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

一、双指针法

关键点总结

1. 三个指针：pre（前驱）、cur（当前）、temp（临时保存）

2. 核心操作：cur.next = pre 实现指针反转

3. 防止断链：用temp保存下一个节点

4. 指针移动：pre和cur同步向前移动

5. 返回值：pre最终指向新链表的头节点

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

#（版本一）双指针法
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head    # cur指针指向当前要处理的节点，初始为头节点
        pre = None    # pre指针指向当前节点的前一个节点，初始为None
        
        while 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为None
        return 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

关键点总结

1. 递归参数：cur（当前处理节点）、pre（前驱节点）

2. 终止条件：cur == None 时返回 pre

3. 递归关系：处理当前节点 + 递归处理剩余节点

4. 空间开销：每次递归调用都会占用栈空间

5. 返回值传递：每层递归都返回最终的新头节点

优点：代码简洁，体现递归思维
缺点：空间复杂度较高，深度链表可能栈溢出