当前位置：首页 > news >正文

链表题解——反转链表【LeetCode】

news 2025/8/12 11:44:18

一、双指针法

关键点总结

三个指针：pre（前驱）、cur（当前）、temp（临时保存）
核心操作：cur.next = pre 实现指针反转
防止断链：用temp保存下一个节点
指针移动：pre和cur同步向前移动
返回值：pre最终指向新链表的头节点

时间复杂度：O(n) - 需要遍历每个节点一次
空间复杂度：O(1) - 只使用了常数个额外变量

#（版本一）双指针法
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:cur = head    # cur指针指向当前要处理的节点，初始为头节点pre = None    # pre指针指向当前节点的前一个节点，初始为Nonewhile cur:    # 当还有节点需要处理时继续循环temp = cur.next      # 临时保存当前节点的下一个节点，防止断链后丢失cur.next = pre       # 将当前节点的next指针反向，指向前一个节点pre = cur           # pre指针向前移动，更新为当前节点cur = temp          # cur指针向前移动，指向下一个要处理的节点return pre    # 循环结束后，pre指向原链表的最后一个节点，即新链表的头节点

执行过程示例

假设原链表为：1 -> 2 -> 3 -> None

初始状态:
pre = None, cur = 1 -> 2 -> 3 -> None第1次循环:
temp = 2 -> 3 -> None    # 保存下一个节点
1 -> None               # cur.next = pre
pre = 1, cur = 2 -> 3 -> None第2次循环:
temp = 3 -> None        # 保存下一个节点  
2 -> 1 -> None          # cur.next = pre
pre = 2, cur = 3 -> None第3次循环:
temp = None             # 保存下一个节点
3 -> 2 -> 1 -> None     # cur.next = pre  
pre = 3, cur = None循环结束，返回pre = 3 -> 2 -> 1 -> None

二、递归法

算法思路

这是递归法实现链表反转，核心思想是：将反转操作分解为当前节点的反转 + 递归处理剩余节点。

#（版本二）递归法
class Solution:def reverseList(self, head: ListNode) -> ListNode:# 主函数：调用递归辅助函数，初始时pre为Nonereturn self.reverse(head, None)def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:# 递归终止条件：当前节点为空，说明已处理完所有节点if cur == None:return pre    # 返回pre，此时pre指向原链表的最后一个节点（新链表头节点）# 保存当前节点的下一个节点，防止断链temp = cur.next# 反转当前节点：将当前节点指向前一个节点cur.next = pre# 递归处理：继续处理下一个节点# 参数：temp（下一个要处理的节点），cur（作为下一轮的pre）return self.reverse(temp, cur)

递归执行过程示例

假设原链表为：1 -> 2 -> 3 -> None

调用栈展开过程：reverse(1->2->3->None, None)
├── temp = 2->3->None
├── 1.next = None  (1->None)
└── return reverse(2->3->None, 1->None)reverse(2->3->None, 1->None)  ├── temp = 3->None├── 2.next = 1->None  (2->1->None)└── return reverse(3->None, 2->1->None)reverse(3->None, 2->1->None)├── temp = None  ├── 3.next = 2->1->None  (3->2->1->None)└── return reverse(None, 3->2->1->None)reverse(None, 3->2->1->None)└── return 3->2->1->None  # 递归终止调用栈回溯过程：
所有递归调用都返回 3->2->1->None