题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
解法分析
可以使用双指针法或者递归法
Python写法
双指针法
- 双指针法注意循环的条件为current为真，最终的返回值应该时pre；
- 如果循环条件是current.next为真，由于在第一个循环中current.next会被赋值为None，所以会报错或者跳出循环，导致逻辑错误。
# 定义链表
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]:
# 双指针法
temp = ListNode()
current = head
pre = None
while current:
# 保存current.next
temp = current.next
# 将current指向pre
current.next = pre
# pre前进一个节点
pre = current
# current前进一个节点
current = temp
return pre
递归写法
注意递归结束的条件
# 双指针法
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverse(self, pre: ListNode, current: ListNode):
if current == None:
return pre
temp = current.next
current.next = pre
# 实际上时更新pre和current到下一个节点
# pre = current
# current = temp
return self.reverse(current, temp)
def reverse_list(self, head: ListNode):
# 初始化pre和current
# pre = None
# current = head
return self.reverse(None, head)
