← 上一课第 5 课 / 40下一课 →

🔗 链表 — 指针的舞蹈

链表是指针操控的基本功，翻转、合并、检测环，面试必考

📖 链表的核心概念

链表（Linked List）是一种线性数据结构，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中不连续存储，插入删除 O(1)，但随机访问 O(n)。链表问题的核心是指针操作——正确地断开和重连指针。

链表的结构: 单链表: head → [1|●]→ [2|●]→ [3|●]→ [4|●]→ None val next val next val next val next 双链表: None ←[●|1|●]⇄[●|2|●]⇄[●|3|●]→ None prev val next 常见操作: ┌─────────────┬──────────┬──────────┐ │ 操作 │ 数组 │ 链表 │ ├─────────────┼──────────┼──────────┤ │ 随机访问 │ O(1) │ O(n) │ │ 头部插入 │ O(n) │ O(1) │ │ 尾部插入 │ O(1)均摊 │ O(n)/O(1)│ │ 中间插入/删除│ O(n) │ O(1)* │ └─────────────┴──────────┴──────────┘ * 已知位置的前提下

1. 链表操作的黄金法则

画图！画图！画图！
链表问题最重要的技巧是在纸上画出指针指向，然后按步骤修改。
错误根源：指针还没断就重连，导致链断裂。
虚拟头节点（dummy node）：
处理头节点可能被删除的情况，统一操作逻辑。
dummy = ListNode(0, head)，最后返回 dummy.next
好处：不用特殊处理头节点，代码更简洁
指针操作的顺序：
先保存要断开的节点 → 再修改指针 → 最后推进。
核心：不要丢失任何节点的引用！

2. LeetCode 链表节点定义

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

🎯 题目一：合并两个有序链表 (LC 21)

题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例: list1 = [1,2,4], list2 = [1,3,4] list1: 1 → 2 → 4 → None list2: 1 → 3 → 4 → None 合并过程: dummy → 1(list1) → 1(list2) → 2(list1) → 3(list2) → 4(list1) → 4(list2) → None 结果: [1, 1, 2, 3, 4, 4]

思路分析

迭代法：用 dummy 节点简化操作，双指针分别遍历两个链表。
每次取较小的节点接到结果链表末尾，移动对应指针。
当一个链表遍历完，直接接上另一个链表的剩余部分。
时间复杂度：O(n+m)，空间复杂度：O(1)
递归法：更优雅，但空间 O(n+m)。
比较两个头节点，较小者的 next 指向递归合并剩余部分的结果。
递归基：一个链表为空，返回另一个。

代码实现

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cur = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dummy.next

复杂度分析

时间复杂度：O(n+m) — 每个节点访问一次

空间复杂度：O(1) — 只用指针，不创建新节点

变体练习

🎯 题目二：反转链表 (LC 206)

题目描述：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例: head = [1, 2, 3, 4, 5] 反转前: 1 → 2 → 3 → 4 → 5 → None 反转后: None ← 1 ← 2 ← 3 ← 4 ← 5 迭代过程 (三指针): prev=None, curr=1 Step 1: next=2, curr.next=None, prev=1, curr=2 None ← 1 2 → 3 → 4 → 5 → None Step 2: next=3, curr.next=1, prev=2, curr=3 None ← 1 ← 2 3 → 4 → 5 → None Step 3: next=4, curr.next=2, prev=3, curr=4 None ← 1 ← 2 ← 3 4 → 5 → None Step 4: next=5, curr.next=3, prev=4, curr=5 None ← 1 ← 2 ← 3 ← 4 5 → None Step 5: next=None, curr.next=4, prev=5, curr=None None ← 1 ← 2 ← 3 ← 4 ← 5 返回 prev=5

思路分析

迭代法（推荐）：用 prev、curr、next 三个指针。
1. 保存 curr.next → next
2. 翻转 curr.next → prev
3. 推进 prev → curr, curr → next
时间复杂度：O(n)，空间复杂度：O(1)
递归法：递归到末尾，从后往前翻转。
new_head = reverseList(head.next)
head.next.next = head
head.next = None
时间复杂度：O(n)，空间复杂度：O(n)（递归栈）

代码实现

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

复杂度分析

时间复杂度：O(n) — 一次遍历

空间复杂度：O(1) — 只用三个指针

反转链表是链表操作的基石！很多高级题目都用到：反转前 N 个、反转区间 [m,n]、K 个一组反转。务必熟练掌握。

变体练习

🎯 题目三：回文链表 (LC 234)

题目描述：给你一个单链表的头节点 head，请你判断该链表是否为回文链表。

示例: head = [1, 2, 2, 1] 方法: 找中点 + 反转后半 + 比较 Step 1: 快慢指针找中点 1 → 2 → 2 → 1 → None ↑slow ↑fast 中点: 第二个2 Step 2: 反转后半 1 → 2 → None None ← 2 ← 1 ↑head ↑mid Step 3: 双指针比较 1==1 ✓, 2==2 ✓ → 是回文!

思路分析

找中点 + 反转 + 比较：三步走，O(n) 时间 O(1) 空间。
1. 快慢指针找中点：fast 走两步，slow 走一步，fast 到末尾时 slow 在中点
2. 反转后半段：从 slow 开始反转
3. 双指针比较：从头和反转后的头开始比较
时间复杂度：O(n)，空间复杂度：O(1)

代码实现

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 1. 快慢指针找中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 2. 反转后半段
        prev = None
        curr = slow
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        # 3. 双指针比较
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

复杂度分析

时间复杂度：O(n) — 三次遍历（找中点+反转+比较）

空间复杂度：O(1) — 只用指针

如果要求不能修改原链表，需要在比较完后恢复反转的部分。面试中可以先提这个要求。

变体练习

成就解锁：链表舞者 — 掌握合并、反转、回文判断三大链表核心操作
LeetCode AC验证：LC 21 Merge Two Sorted Lists ✅ | LC 206 Reverse Linked List ✅ | LC 234 Palindrome Linked List ✅

📝 课后练习

  1. LC 141 环形链表（快慢指针检测环）
  2. LC 160 相交链表（双指针交叉遍历）
  3. LC 19 删除链表的倒数第 N 个节点（快慢指针）
  4. LC 876 链表的中间节点（快慢指针）
  5. LC 83 删除排序链表中的重复元素

🔑 本课要点回顾

📚 扩展阅读

思考题：如何判断两个链表是否相交？如果相交，如何找到交点？提示：让两个指针分别遍历 A+B 和 B+A，它们一定在交点相遇。

🔬 链表的高级技巧

链表问题有一些固定套路，掌握这些套路可以快速解决大部分链表题。

1. 两条链表相交问题

找两条链表的交点（LC 160）：让两个指针分别遍历 A+B 和 B+A，它们一定在交点相遇。

def getIntersectionNode(headA, headB):
    pA, pB = headA, headB
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

2. 环的入口节点

LC 142 环形链表 II：快慢指针找到相遇点后，一个指针从头部出发，另一个从相遇点出发，两者相遇即为环的入口。

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            p = head
            while p != slow:
                p = p.next
                slow = slow.next
            return p
    return None
链表题的终极心法：画图！无论多简单的链表题，先在纸上画出指针指向，按步骤模拟，就不会出错。