反转链表

问题拆解

要把 1 -> 2 -> 3 -> 4 -> 5 变成 5 -> 4 -> 3 -> 2 -> 1。链表不像数组能随机访问，只能顺着 next 一步步走，所以反转的动作只能落在“改写每个节点的 next 指向”上。

问题在于：当我们把 cur.next 从指向后继改成指向前驱时，原来的后继就找不到了。所以真正的关键是在改指针之前，先用一个变量把后继存下来。

反转链表不需要额外的容器，需要的是三个指针：已经反转好的前半段、当前节点、还没处理的后继。

迭代：三指针

def reverseList(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

prev 是已经反转好的部分的头，初始为 None（反转后原来的头会变成尾，尾的 next 正是 None）。每一轮先存后继，再让当前节点掉头指向 prev，然后两个指针一起前移。循环结束时 cur 走到空，prev 恰好停在原链表的最后一个节点，也就是新的头。

递归

题目进阶希望两种写法都掌握。递归的思路是：先反转从 head.next 开始的子链表，拿回它的新头，再把 head 接到子链表的末尾。

def reverseList(head):
    if head is None or head.next is None:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

关键的两行是 head.next.next = head（让后继反过来指向自己）和 head.next = None（断开原来的正向指针，否则会形成环）。new_head 在整条递归里一路向上原样返回，始终是原链表的尾节点。

复杂度

指标	复杂度	原因
时间	O(n)	每个节点只访问一次
空间	O(1) / O(n)	迭代只用常数指针；递归的栈深度是链表长度

可以迁移的模式

• 需要原地改写指针时，先用临时变量保住后继，再动手；
• prev / cur / nxt 三指针是链表操作的基本手型；
• 递归写法把“反转整条”拆成“反转子链表 + 接回当前节点”。

一旦习惯了“存后继—改指针—前移”这套动作，后面很多链表题都是它的变体。