链表：反转与快慢指针

1.3 链表：反转与快慢指针

本节摘要：链表拿走了数组的随机访问能力，于是数组上的进化套路集体失效，新的武器应运而生。本节以反转链表与快慢指针为两个主战场，演示"用指针的移动代替下标的跳跃"这条进化逻辑，覆盖迭代反转、找中点、判环三大高频考点。

结构变了，套路跟着变

承接两数之和的进化经验，本节把场景换成链表。数组的本事来自连续内存：知道下标就能一步跳到任何位置。链表恰好相反，每个节点只认识自己的下一个邻居，想知道第五个节点是什么，只能从头开始走五步。这个差异决定了一切：数组上 O(1) 的随机访问在链表上是 O(n)，而数组上要 O(n) 的"在头部插入"，链表上反而是 O(1)。所以链表题的进化方向从来不是"怎么跳"，而是"怎么让每个指针都带着最大的信息量移动"。

先给出场景约定。链表节点用 Python 描述如下，后续代码都基于这个定义：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 构造 1 -> 2 -> 3 -> 4 -> None
def build(vals):
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

print(to_list(build([1, 2, 3, 4])))   # 输出 [1, 2, 3, 4]
​

一、反转链表：三个指针的接力

反转是链表题的"握手法则"，必须练到肌肉记忆。朴素的思路是先把值抄进数组、反转数组再抄回去——能跑通，但要 O(n) 额外空间，面试官听到就会摇头。进化方向是原地反转：维护三个指针，prev 指向已反转部分的头，cur 指向待处理的节点，用临时变量 nxt 暂存 cur 的下一个，然后把 cur 的箭头调头指向 prev，三个指针整体前移。走完一趟，箭头全部调头。

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # 先记住去哪
        cur.next = prev     # 箭头调头
        prev = cur          # prev 前进
        cur = nxt           # cur 前进
    return prev             # prev 停在新的头

h = build([1, 2, 3, 4])
print(to_list(reverse_list(h)))    # 输出 [4, 3, 2, 1]
​

时间 O(n)，每节点处理一次；空间 O(1)，只用了三个变量。这里最容易犯的错是不用临时变量就敢改 next——箭头一断，后面的节点就永远找不回来了。调试链表题的铁律：改任何指针之前，先确认"还有没有别的路能到那个节点"。递归写法也能反转链表，代码更短但空间是 O(n)（调用栈），面试中可以口头提一句，体现你懂两条路线的取舍。

二、快慢指针：一箭三雕

快慢指针的核心思想：让两个指针同向出发但速度不同，它们的"距离差"本身就成了信息源。第一应用，找中点。朴素做法先数一遍长度 n，再走二分之 n 步，两趟扫描。进化版只走一趟：慢指针每次走一步，快指针每次走两步，快指针到头时慢指针恰好在中点。奇偶长度的差别要当场跟面试官确认清楚——节点数为偶数时，慢指针停在中间偏后的那个。

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

print(middle_node(build([1, 2, 3, 4, 5])).val)    # 输出 3
print(middle_node(build([1, 2, 3, 4])).val)       # 输出 3
​

第二应用，判环。如果链表某个节点的 next 指回了前面的节点，遍历就会永远出不去，朴素做法靠哈希表记下见过的节点，空间 O(n)。进化版回到快慢指针：一旦有环，快指针一定会在环里追上慢指针——就像环形跑道上跑得快的人迟早套圈。两指针相遇说明有环；快指针先到 None 说明无环。再进一步，相遇后把一个指针放回头部，两个指针同速前进，再次相遇处就是环的入口，这是著名的弗洛伊德判圈法的完整形态。

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def detect_cycle_entry(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            p = head
            while p is not slow:
                p, slow = p.next, slow.next
            return p
    return None
​

第三应用，删除倒数第 k 个节点。朴素做法同样要两趟：先数长度再定位。进化版让快指针先走 k 步，然后快慢一起走，快指针到尾时慢指针的下一个就是要删的节点——一趟完成。三个应用，同一个思想：速度差或提前量制造了固定的距离关系，而距离关系携带了定位信息。

快慢指针的距离差如何携带信息

三、哑节点与边界

链表题的边界灾难几乎都发生在头部：删头、头就是中点、头就是环入口。通用解法是哑节点（dummy node）——在真正的头之前挂一个占位节点，让"删除头节点"与"删除中间节点"变成同一段代码，结尾返回 dummy.next 即可。这个技巧没有任何复杂度收益，却能把边界分支砍掉一半，属于纯赚的工程习惯。练习建议：把本节三个应用各手写两遍，第二遍不看任何资料，并在纸上画出指针每步的位置。链表是所有数据结构里最依赖画图debug的，纸上演练一次胜过盲改十次。

本节要点回顾

• 链表题的进化方向：不追求跳跃访问，而是让指针的移动携带最多信息；
• 原地反转三指针：暂存、调头、双前进，全程 O(n) 时间 O(1) 空间，必须练到默写；
• 快慢指针一箭三雕：找中点、判环、删倒数第 k 个，本质都是用速度差或提前量定位；
• 判环进阶：相遇后回起点同速再走，二次相遇即环入口；
• 哑节点是边界保险：把头部特判统一成普通分支，删头不再特殊。

下一节面对排序这个古老问题：进化链将首次撞上理论天花板——比较排序存在不可突破的下界。