E206.反转链表

three pinters, recursion, https://leetcode.cn/problems/reverse-linked-list/

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

使用三个指针（prev, current, next_node）迭代整个链表，将当前节点的 next 指针指向前一个节点，从而实现链表反转，最后返回 prev 作为新的头节点。

python

# 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
        current = head
        while current:
            next_node = current.next
            current.next = pre
            pre = current
            current = next_node

        return pre

递归的反转写法

python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head  # 基本情况：空链表或只有一个节点的链表直接返回头节点
        p = self.reverseList(head.next)  # 递归反转剩余链表
        head.next.next = head  # 反转当前节点的指针
        head.next = None  # 设置当前节点的next为None
        return p  # 返回新的头节点

【# 汤伟杰，信息管理系】
思路：这是在寒假期间做的，当时被递归的写法迷惑了一下午。递归的思路妙就妙在这个函数的返回值上：
在链表不为空或者长度不为1的时候，这个函数体的第一行就进行了函数调用，并将返回值赋给了reversed_head；然后整个函数返回的也是这个reversed_head。经过一阵思考才发现，哦，原来这一行函数调用，实际上是调用了n次（n是链表长度-1），也就是说，一旦调用了这个函数，就会一直调用到这个链表的最后一个节点，才会达到退出条件，并返回这个最终节点。而实际上，它就是想要的最终返回结果，因此把这个节点直接赋值给reversed_head，同时通过将整个函数的返回值也设置为这个变量以保证在回溯时该变量能够不断原地赋值（自己给自己赋值）。因此，在调用递归函数这一行的下面两行，实际上是在对当前递归到的节点的下一个节点的next指针调整到自己身上，并且把自己的当前next指针调整为None，这样也保证了链表的单向性。总之，这个递归很烧脑，但是想清楚了很通透！

这段递归反转链表的写法，做一个逐层剖析。它“烧脑”的地方确实在于：函数返回值的传递 + 回溯时指针的调整。
代码
python
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head  # 递归出口：空链表或最后一个节点
        
        p = self.reverseList(head.next)  # 递归反转子链表
        head.next.next = head  # 将子链表的尾部指向自己
        head.next = None       # 断开自己和子链表的旧连接
        return p               # 返回新的头节点
分解理解
递归出口
python
if head is None or head.next is None:
    return head
当到达最后一个节点（或空链表）时，直接返回它。
关键点：这个返回值会在整个递归回溯过程中，一直“往上传递”，最终成为新链表的头。
递归调用
python
p = self.reverseList(head.next)
假设链表是 1 -> 2 -> 3 -> 4 -> 5。
当 head = 1 时，这行代码会不断调用自己，直到 head = 5 时触发退出条件。
从最深层开始返回，p 永远是“反转后的新链表的头节点”。
所以不论当前递归在哪一层，p 始终指向 5。
回溯阶段的指针翻转
python
head.next.next = head
head.next = None
当递归回到 head = 4 时：
head.next 是 5，
所以 head.next.next = head 把 5.next 指向 4，形成 5 -> 4。
然后 head.next = None 把 4 的旧指向断开，避免链表成环。
回溯到 head = 3：
head.next 是 4（但现在 4 -> None，5 -> 4），
所以 head.next.next = head，把 4.next 指向 3，形成 5 -> 4 -> 3。
再断开 3 -> 4 的旧链。
一直回溯到 head = 1，最终形成 5 -> 4 -> 3 -> 2 -> 1。
返回新头节点
python
return p
不管在哪一层递归，p 都指向 反转后的新链表的头（也就是最初的尾节点）。
所以最终 reverseList(head) 返回的就是整个新链表的头节点。
递归反转的精髓
递归到底 → 找到最后一个节点，作为新头。
回溯时翻转 → 把“下一个节点”的 next 指向自己。
断开旧链路 → 避免形成环。
始终返回新头 → 保证调用链一路把新头传上来。
小技巧
想象一下栈：
递归入栈：一路走到链表的最后。
递归出栈：在出栈时逐一“掉头”，像一行人走到尽头，逐个转身，最终整个队伍方向掉转。

E206.反转链表 ​

E206.反转链表