链表在真实工程里无处不在:LRU 缓存、哈希表的链地址法、文件系统的目录结构……而面试里它更是常客。这篇文章我们用 Python 从零手写链表,把反转链表、判断环、找中点这三类必考题型一次讲透,所有代码复制就能跑。

1. 链表:用指针串起来的节点

数组在内存里是一段连续空间,链表则相反——它的每个元素(叫节点)散落在内存各处,靠"指向下一个节点"的指针串成一条链。每个节点通常有两个字段:val 存数据,next 存下一个节点的引用。链表的最后一个节点 next 指向 None,表示链的尽头。

为什么要有链表?对比数组:数组随机访问快(O(1)),但中间插入删除要搬动后面的元素(O(n));链表恰好反过来——只要改两个指针就能完成插入删除(O(1)),但想找第 k 个元素只能从头一个个走(O(n))。工程里没有绝对优劣,只有场景适配。

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

def build_list(nums):
    """用数组构造链表,返回头节点"""
    dummy = ListNode()      # 哨兵节点,简化边界处理
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

def show(head):
    vals = []
    while head:
        vals.append(str(head.val))
        head = head.next
    print(" -> ".join(vals))

head = build_list([1, 2, 3, 4, 5])
show(head)   # 1 -> 2 -> 3 -> 4 -> 5

这里有个小技巧值得记住:哨兵节点(dummy)。构造链表时如果直接操作头节点,要单独处理"链表为空"的情况;用 dummy 占位后,所有节点一视同仁,最后返回 dummy.next 即可。这个套路在后续所有链表题里都适用。

2. 反转链表:迭代法

反转链表是链表题"一哥",几乎每场面试都可能出现。迭代思路就一句话:遍历时把每个节点的 next 指向前一个节点。为此需要三个指针:prev 记录前驱,cur 是当前节点,nxt 先保存后继——因为一旦改了 cur.next,原来的后继就丢了。

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next    # 先保存后继
        cur.next = prev   # 指针掉头
        prev = cur        # 前驱前进
        cur = nxt         # 当前前进
    return prev           # 新链表的头

head = build_list([1, 2, 3, 4, 5])
show(reverse_list(head))  # 5 -> 4 -> 3 -> 2 -> 1

新手最容易犯的错是忘了保存 nxt,导致改完 cur.next 后链表断掉、循环无法继续。循环结束时 cur 走到 None,此时 prev 恰好停在原链表的尾节点,也就是新链表的头,直接返回它。

顺便说一句复杂度:迭代反转的时间是 O(n),额外空间只有三个指针,是 O(1);递归版时间同样是 O(n),但调用栈要占 O(n) 空间。面试被问"两版有什么区别"时,这就是标准答案。

3. 反转链表:递归版

递归版更考验对"函数调用栈"的理解。假设 reverse_rec(head.next) 已经帮我们反转好了后半段,现在只需要让 head 接上去:head.next.next = head 意思是"让 head 的下一个节点反过来指向 head",然后断开 head.next 避免成环。

def reverse_rec(head):
    if head is None or head.next is None:
        return head                  # 递归出口:空或只剩一个
    new_head = reverse_rec(head.next)
    head.next.next = head            # 后一个节点指回自己
    head.next = None                 # 断开,防止环
    return new_head

head = build_list([1, 2, 3, 4, 5])
show(reverse_rec(head))  # 5 -> 4 -> 3 -> 2 -> 1

递归代码短,但有两个代价:一是长链表会占用 O(n) 的调用栈空间,极端情况下可能栈溢出;二是"递归出口"写错(比如漏了 head.next is None)会直接死循环。面试时建议先讲迭代版,递归版作为加分项展示理解深度。

4. 快慢指针:找链表中点

快慢指针是链表题最重要的技巧:让 slow 每次走一步、fast 每次走两步。当 fast 走到末尾时,slow 恰好停在中点。它常被用来做归并排序、判断回文链表的预处理。

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

head = build_list([1, 2, 3, 4, 5])
print(middle_node(head).val)          # 3
head2 = build_list([1, 2, 3, 4, 5, 6])
print(middle_node(head2).val)         # 4(偶数长度取靠后那个)

循环条件 fast and fast.next 必须两个都判断:fast 为空说明奇数长度已走完,fast.next 为空说明偶数长度走到倒数第二个,缺一个都会在 fast.next.next 处报 AttributeError。

快慢指针还有一个变体:删除倒数第 k 个节点。让 fast 先走 k 步,然后 slow 和 fast 同步前进,当 fast 走到末尾时,slow 恰好停在倒数第 k 个节点的前一个位置,直接改指针就能删掉目标节点。这个"错位出发"的思路,和找中点是同一套思想。

5. 判断环与寻找环入口

环形链表指某个节点的 next 指回了前面的节点。判断有没有环,快慢指针依然是利器:如果有环,fast 迟早会在环里追上 slow——就像操场跑步,速度快的人总会套圈追上慢的人。

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

# 造一个环:1 -> 2 -> 3 -> 4 -> 2
head = build_list([1, 2, 3, 4])
head.next.next.next.next = head.next
print(has_cycle(head))        # True

注意判断用的是 slow is fast(引用相等)而不是 ==,因为节点是自定义对象,这里比较的是"是不是同一个节点",不是值相等。

进阶问题:不仅要判断有没有环,还要找到环的入口。Floyd 算法的结论是:快慢指针第一次相遇后,让一个新指针 p 从头出发,slow 继续走,两者每次都走一步,再次相遇的位置就是环入口。证明需要一点数学,先记住结论再理解原理。

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p = head
            while p is not slow:   # 同步走,相遇即入口
                p = p.next
                slow = slow.next
            return p
    return None

head = build_list([1, 2, 3, 4])
head.next.next.next.next = head.next
print(detect_cycle(head).val)   # 2

6. 总结与练习

回顾一下这节的核心武器:哨兵节点简化边界;反转链表记住"先存后继再掉头";快慢指针一统"找中点、判环、找环入口"三题。链表题还有个通用心法——画图。把指针关系画出来,代码就是"照着图翻译"。

💡 链表题最容易翻车的地方是边界:空链表、只有一个节点、偶数长度。写完代码后,务必拿这三个 case 在纸上走一遍。

练习题: