给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
注意:本来考虑head和head.next是否为空,最后发现为空也不影响结果。
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: # if head != None and head.next != None: # pre = None # cur = head # while cur != None: # temp = cur.next # cur.next = pre # pre = cur # cur = temp # return pre # return head pre = None cur = head while cur != None: temp = cur.next cur.next = pre pre = cur cur = temp return pre
建议双指针思路,递归直接不容易写,但是根据双指针代码,可以写出递归代码。
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: # pre = None # cur = head # while cur != None: # temp = cur.next # cur.next = pre # pre = cur # cur = temp # return pre return self.reverse(None, head) def reverse(self, pre, cur): while cur != None: temp = cur.next cur.next = pre return self.reverse(cur, temp) return pre