30 秒速览

  • 什么时候用：链表数据结构上的操作
  • 核心技巧：虚拟头节点、快慢指针、反转、画图
  • 时间复杂度：通常 O(n)
  • 空间复杂度：通常 O(1)

一、链表基础

链表 vs 数组

特性数组链表
随机访问O(1)O(n)
插入/删除O(n)O(1)（已知位置）
内存连续分散
大小固定（或动态扩容）灵活

链表节点定义

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

核心操作：画图

链表题最大的坑是指针丢失。解决方案：

  1. 画图：在纸上画出节点和指针
  2. 保存引用：修改前先保存需要的信息
  3. 分步操作：一步一步来，不要跳步
原链表: 1 → 2 → 3 → 4 → 5

删除节点 3：
  1. prev.next = cur.next  （跳过 cur）
  2. 节点 3 自动被回收

结果: 1 → 2 → 4 → 5

二、核心技巧

技巧 1：虚拟头节点

问题：在链表头部插入/删除需要特殊处理。

解决：添加一个虚拟头节点 dummy，统一所有操作。

def insert_at_head(head: ListNode, val: int) -> ListNode:
    dummy = ListNode(0, head)  # 虚拟头

    new_node = ListNode(val)
    new_node.next = dummy.next
    dummy.next = new_node

    return dummy.next  # 返回真正的头

应用场景：

  • 需要删除头节点
  • 需要在头部插入
  • 合并两个链表

技巧 2：快慢指针

应用场景：

  • 检测环
  • 找中点
  • 找倒数第 k 个
# 检测环
def hasCycle(head: ListNode) -> bool:
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

# 找中点
def findMiddle(head: ListNode) -> ListNode:
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

# 找倒数第 k 个
def findKthFromEnd(head: ListNode, k: int) -> ListNode:
    fast = head

    # 快指针先走 k 步
    for _ in range(k):
        if not fast:
            return None
        fast = fast.next

    # 快慢指针同时走
    slow = head
    while fast:
        slow = slow.next
        fast = fast.next

    return slow

技巧 3：反转链表

迭代法

def reverseList(head: ListNode) -> ListNode:
    prev = None
    cur = head

    while cur:
        next_temp = cur.next  # 保存下一个
        cur.next = prev       # 反转
        prev = cur            # 移动 prev
        cur = next_temp       # 移动 cur

    return prev

图解：

原链表: 1 → 2 → 3 → None

初始: prev=None, cur=1
第1步: 1 → None, prev=1, cur=2
第2步: 2 → 1 → None, prev=2, cur=3
第3步: 3 → 2 → 1 → None, prev=3, cur=None

结果: 3 → 2 → 1 → None

递归法

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    # 递归反转后面的部分
    new_head = reverseList(head.next)

    # 反转当前节点
    head.next.next = head
    head.next = None

    return new_head

技巧 4：双指针合并

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    cur = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next

    # 连接剩余部分
    cur.next = l1 if l1 else l2

    return dummy.next

三、典型例题

例题 1：LC 206. 反转链表

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

代码

def reverseList(head: ListNode) -> ListNode:
    prev = None
    cur = head

    while cur:
        next_temp = cur.next
        cur.next = prev
        prev = cur
        cur = next_temp

    return prev

复杂度：时间 O(n)，空间 O(1)

例题 2：LC 92. 反转链表 II

题目：给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

思路

  1. 找到 left 前面的节点 pre
  2. 反转 left 到 right 的部分
  3. 连接回去

代码

def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
    if left == 1:
        return reverseN(head, right)

    # 移动到 left 位置
    head.next = reverseBetween(head.next, left - 1, right - 1)
    return head

def reverseN(head: ListNode, n: int) -> ListNode:
    """反转前 n 个节点"""
    if n == 1:
        return head

    # 反转后面的部分
    new_head = reverseN(head.next, n - 1)

    # 保存第 n+1 个节点
    successor = head.next.next

    # 反转当前节点
    head.next.next = head
    head.next = successor

    return new_head

复杂度：时间 O(n)，空间 O(n)（递归栈）

例题 3：LC 21. 合并两个有序链表

题目：将两个升序链表合并为一个新的升序链表并返回。

代码

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    cur = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next

    cur.next = l1 if l1 else l2

    return dummy.next

复杂度：时间 O(m + n)，空间 O(1)

例题 4：LC 141. 环形链表

题目：给你一个链表的头节点 head，判断链表中是否有环。

代码

def hasCycle(head: ListNode) -> bool:
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

为什么快慢指针能检测环？

如果有环，快指针最终会追上慢指针（想象操场上跑步，快的人会套圈慢的人）。

复杂度：时间 O(n)，空间 O(1)

例题 5：LC 142. 环形链表 II

题目：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

思路

  1. 快慢指针找到相遇点
  2. 一个指针从头部出发，一个从相遇点出发，再次相遇就是环入口

数学证明：

设：
- 头到环入口距离为 a
- 环入口到相遇点距离为 b
- 相遇点到环入口距离为 c
- 环长 = b + c

慢指针走了：a + b
快指针走了：a + b + k(b + c)，其中 k ≥ 1

快指针速度是慢指针两倍：
a + b + k(b + c) = 2(a + b)
a = c + (k-1)(b + c)

所以：从头走 a 步 = 从相遇点走 c 步 + 可能绕几圈
即：两个指针分别从头和相遇点出发，会在环入口相遇

代码

def detectCycle(head: ListNode) -> ListNode:
    # 快慢指针找相遇点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # 无环

    # 两个指针分别从头和相遇点出发
    ptr1 = head
    ptr2 = slow

    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    return ptr1

复杂度：时间 O(n)，空间 O(1)

例题 6：LC 19. 删除链表的倒数第 N 个结点

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

代码

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0, head)
    fast = slow = dummy

    # 快指针先走 n 步
    for _ in range(n):
        fast = fast.next

    # 快慢指针同时走
    while fast.next:
        fast = fast.next
        slow = slow.next

    # 删除倒数第 n 个
    slow.next = slow.next.next

    return dummy.next

复杂度：时间 O(n)，空间 O(1)

例题 7：LC 160. 相交链表

题目：给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。

思路

让两个指针分别走 A+B 和 B+A 的路径，如果有交点，会在交点相遇。

A: a1 → a2 → c1 → c2 → c3
B: b1 → b2 → b3 → c1 → c2 → c3

pA 路径: a1 → a2 → c1 → c2 → c3 → b1 → b2 → b3 → c1
pB 路径: b1 → b2 → b3 → c1 → c2 → c3 → a1 → a2 → c1

pA 和 pB 在 c1 相遇！

代码

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None

    pA, pB = headA, headB

    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA

    return pA  # 相交节点或 None

复杂度：时间 O(m + n)，空间 O(1)

例题 8：LC 234. 回文链表

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

思路

  1. 快慢指针找中点
  2. 反转后半部分
  3. 比较前后两部分
  4. （可选）恢复链表

代码

def isPalindrome(head: ListNode) -> bool:
    # 找中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 反转后半部分
    prev = None
    cur = slow
    while cur:
        next_temp = cur.next
        cur.next = prev
        prev = cur
        cur = next_temp

    # 比较
    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)

例题 9：LC 148. 排序链表

题目：给你链表的头结点 head，请将其按升序排列并返回排序后的链表。要求 O(n log n) 时间复杂度和常数级空间复杂度。

思路

归并排序：

  1. 找中点
  2. 递归排序两半
  3. 合并

代码

def sortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    # 找中点（用快慢指针，注意要断开）
    slow = fast = head
    prev = None
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    prev.next = None  # 断开

    # 递归排序
    left = sortList(head)
    right = sortList(slow)

    # 合并
    return merge(left, right)

def merge(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    cur = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next

    cur.next = l1 if l1 else l2
    return dummy.next

复杂度：时间 O(n log n)，空间 O(log n)（递归栈）

四、常见错误与陷阱

错误 1：指针丢失

# 错误：直接修改，丢失了 next
cur.next = new_node
new_node = cur.next  # new_node 是刚才赋值的，不是原来的 next！

# 正确：先保存
next_temp = cur.next
cur.next = new_node
new_node.next = next_temp

错误 2：忘记虚拟头

# 错误：删除头节点时需要特殊处理
if head.val == target:
    head = head.next  # 需要更新 head

# 正确：使用虚拟头，统一处理
dummy = ListNode(0, head)
# ... 操作 ...
return dummy.next

错误 3：快慢指针初始位置

# 找中点时，如果需要断开，要记住前一个节点
slow = fast = head
prev = None  # 记住 slow 的前一个

while fast and fast.next:
    prev = slow
    slow = slow.next
    fast = fast.next.next

prev.next = None  # 断开

错误 4：环检测忘记处理边界

# 错误：空链表会出错
while fast.next:  # fast 可能是 None

# 正确：先检查 fast
while fast and fast.next:

五、复盘清单

触发信号

  • 链表数据结构
  • 需要反转
  • 需要找中点/倒数第 k 个
  • 需要检测环
  • 需要合并

边界条件

  • 空链表
  • 单节点链表
  • 两节点链表
  • 删除头节点
  • 删除尾节点

常见错误

  • 指针丢失
  • 忘记虚拟头
  • 快慢指针边界
  • 没有断开链表

六、题目清单

基础题

题号题目难度考点
206反转链表Easy反转
21合并两个有序链表Easy合并
141环形链表Easy快慢指针
876链表的中间结点Easy快慢指针
19删除倒数第 N 个Medium快慢指针

进阶题

题号题目难度考点
92反转链表 IIMedium反转区间
142环形链表 IIMedium环入口
160相交链表Easy双指针
234回文链表Easy中点+反转
148排序链表Medium归并排序
23合并 K 个升序链表Hard堆/分治