03 链表详细教学

链表题的核心动作：

// dummy
// 找中点
// 反转
// 合并
// 局部断开再接回

代表题

Reverse Linked List

这个题型 / 算法点的总结

Reverse Linked List 主要在练链表指针操作，重点是想清楚节点之间该怎么断开、反转和接回去。

题目含义

反转链表的标准做法是维护两个指针：

  • prev：已经反转好的部分头节点
  • cur：当前要处理的节点

每一步都先保存 next，再把当前节点指向 prev。

代表 Python 代码

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


from typing import Optional

class Solution:
    def reverseList(self, head: Optional['ListNode']) -> Optional['ListNode']:
        prev = None
        cur = head

        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        return prev

时间复杂度

O(n)。

空间复杂度

O(1)。

怎么想到这个方法

先看题型识别里的信号：这题本质上就是 链表反转模板 / Linked List Reversal。把题目翻译成这个模板后，再去套对应的不变量、状态定义或数据结构，就会更容易写出来。

示例 case

  • 输入链表：1 -> 2 -> 3 -> 4 -> 5
  • 输出链表：5 -> 4 -> 3 -> 2 -> 1。整个链表方向被反过来。

常见 Follow-up

  • 能不能把空间复杂度再压缩一层？
  • 有没有另一种常见模板也能解决这题？

Reverse Linked List II

这个题型 / 算法点的总结

Reverse Linked List II 主要在练链表指针操作，重点是想清楚节点之间该怎么断开、反转和接回去。

题目含义

这题是“只反转一段区间”。
关键是先找到反转区间前一个节点 prev，然后对区间做头插法重排。

为什么要用 dummy：

  • 如果反转区间从头节点开始，dummy 可以统一处理

代表 Python 代码

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


from typing import Optional

class Solution:
    def reverseBetween(self, head: Optional['ListNode'], left: int, right: int) -> Optional['ListNode']:
        dummy = ListNode(0, head)
        prev = dummy

        for _ in range(left - 1):
            prev = prev.next

        cur = prev.next
        for _ in range(right - left):
            nxt = cur.next
            cur.next = nxt.next
            nxt.next = prev.next
            prev.next = nxt

        return dummy.next

时间复杂度

O(n)。

空间复杂度

O(1)。

怎么想到这个方法

先看题型识别里的信号：这题本质上就是 局部链表反转 / Partial Linked List Reversal。把题目翻译成这个模板后，再去套对应的不变量、状态定义或数据结构，就会更容易写出来。

示例 case

  • 输入：长度较短的链表样例
  • 输出：按题目要求返回重排、反转、合并或判断结果。链表题建议先画指针再写代码。

常见 Follow-up

  • 能不能把空间复杂度再压缩一层？
  • 有没有另一种常见模板也能解决这题？

Reorder List

这个题型 / 算法点的总结

Reorder List 主要在练链表指针操作，重点是想清楚节点之间该怎么断开、反转和接回去。

题目含义

题目要求把链表重排成：

L0 -> Ln -> L1 -> Ln-1 -> ...

标准做法分三步：

  1. 快慢指针找中点
  2. 反转后半段
  3. 前后两段交替合并

代表 Python 代码

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


from typing import Optional

class Solution:
    def reorderList(self, head: Optional['ListNode']) -> None:
        if not head or not head.next:
            return

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

        prev, cur = None, slow.next
        slow.next = None
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        first, second = head, prev
        while second:
            n1, n2 = first.next, second.next
            first.next = second
            second.next = n1
            first, second = n1, n2

时间复杂度

O(n)。

空间复杂度

O(1)。

怎么想到这个方法

先看题型识别里的信号：这题本质上就是 找中点 + 反转 + 合并 / Split + Reverse + Merge。把题目翻译成这个模板后，再去套对应的不变量、状态定义或数据结构，就会更容易写出来。

示例 case

  • 输入：长度较短的链表样例
  • 输出：按题目要求返回重排、反转、合并或判断结果。链表题建议先画指针再写代码。

常见 Follow-up

  • 能不能把空间复杂度再压缩一层？
  • 有没有另一种常见模板也能解决这题？

Remove Nth Node From End

这个题型 / 算法点的总结

Remove Nth Node From End 的核心是先识别它最像哪种经典题型，再把题目翻译成那个模板。

题目含义

让 fast 先走 n 步，然后 slow 和 fast 一起走。
这样当 fast 到达末尾时，slow 正好在待删除节点前一个位置。

为什么要用 dummy：

  • 如果删除的是头节点，dummy 能统一处理

代表 Python 代码

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


from typing import Optional

class Solution:
    def removeNthFromEnd(self, head: Optional['ListNode'], n: int) -> Optional['ListNode']:
        dummy = ListNode(0, head)
        fast = slow = dummy

        for _ in range(n):
            fast = fast.next

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

        slow.next = slow.next.next
        return dummy.next

时间复杂度

O(n)。

空间复杂度

O(1)。

怎么想到这个方法

先看题型识别里的信号：这题本质上就是 快慢指针 / Two Pointers。把题目翻译成这个模板后，再去套对应的不变量、状态定义或数据结构，就会更容易写出来。

示例 case

  • 输入：一个最小可手算的样例
  • 输出：先手推一遍算法流程，再对照代码中的循环、状态或数据结构变化。

常见 Follow-up

  • 如果输入先排序或已经有序，能不能进一步简化？
  • 如果要返回具体区间或下标，代码里要额外维护什么？

Add Two Numbers / Add Two Numbers II

这个题型 / 算法点的总结

Add Two Numbers / Add Two Numbers II 的核心是先识别它最像哪种经典题型，再把题目翻译成那个模板。

题目含义

这题和手算加法完全一样：

  • 当前位 = 两个节点值 + 进位
  • 结果节点保存 total % 10
  • 新进位是 total // 10

因为输入本身是逆序，所以我们直接从头往后加。

代表 Python 代码

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


from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional['ListNode'], l2: Optional['ListNode']) -> Optional['ListNode']:
        dummy = ListNode()
        cur = dummy
        carry = 0

        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            total = x + y + carry

            carry = total // 10
            cur.next = ListNode(total % 10)
            cur = cur.next

            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

时间复杂度

O(max(m,n))。

空间复杂度

O(1) 额外空间，不计答案链表。

怎么想到这个方法

先看题型识别里的信号：这题本质上就是 链表模拟加法 / Linked List Addition。把题目翻译成这个模板后，再去套对应的不变量、状态定义或数据结构，就会更容易写出来。

示例 case

  • 输入：一个最小可手算的样例
  • 输出：先手推一遍算法流程，再对照代码中的循环、状态或数据结构变化。

常见 Follow-up

  • 能不能把空间复杂度再压缩一层？
  • 有没有另一种常见模板也能解决这题？

Merge k Sorted Lists

这个题型 / 算法点的总结

Merge k Sorted Lists 主要在练链表指针操作，重点是想清楚节点之间该怎么断开、反转和接回去。

题目含义

合并两个有序链表可以双指针，但合并 k 个时最自然的是堆。
堆里维护每条链表当前头节点：

  • 每次弹出最小节点接到答案后面
  • 再把它的 next 放回堆中

代表 Python 代码

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


import heapq
from typing import List, Optional

class Solution:
    def mergeKLists(self, lists: List[Optional['ListNode']]) -> Optional['ListNode']:
        heap = []

        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        dummy = ListNode()
        tail = dummy

        while heap:
            _, i, node = heapq.heappop(heap)
            tail.next = node
            tail = tail.next

            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))

        return dummy.next

时间复杂度

O(N log k)。

空间复杂度

O(k)。

怎么想到这个方法

先看题型识别里的信号：这题本质上就是 堆 / Min Heap。把题目翻译成这个模板后，再去套对应的不变量、状态定义或数据结构，就会更容易写出来。

示例 case

  • 输入：多个已排序链表
  • 输出：合并后的有序链表。最常见做法是最小堆，每次拿当前最小头节点。

常见 Follow-up

  • 如果 k 很小，为什么堆通常比全排序更合适？
  • 如果数据流持续到来，解法要怎么调整？

Sort List

这个题型 / 算法点的总结

Sort List 主要在练链表指针操作，重点是想清楚节点之间该怎么断开、反转和接回去。

题目含义

链表不适合快速排序，因为随机访问不方便。
归并排序更自然：

  1. 找中点拆成两半
  2. 递归排序左右两半
  3. 再合并两个有序链表

代表 Python 代码

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


from typing import Optional

class Solution:
    def sortList(self, head: Optional['ListNode']) -> Optional['ListNode']:
        if not head or not head.next:
            return head

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

        mid = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(mid)
        return self.merge(left, right)

    def merge(self, a: Optional['ListNode'], b: Optional['ListNode']) -> Optional['ListNode']:
        dummy = ListNode()
        tail = dummy

        while a and b:
            if a.val <= b.val:
                tail.next = a
                a = a.next
            else:
                tail.next = b
                b = b.next
            tail = tail.next

        tail.next = a or b
        return dummy.next

时间复杂度

O(n log n)。

空间复杂度

O(log n) 递归栈。

怎么想到这个方法

先看题型识别里的信号：这题本质上就是 链表归并排序 / Merge Sort on Linked List。把题目翻译成这个模板后，再去套对应的不变量、状态定义或数据结构，就会更容易写出来。

示例 case

  • 输入：4 -> 2 -> 1 -> 3
  • 输出：1 -> 2 -> 3 -> 4。链表排序通常用归并最稳定。

常见 Follow-up

  • 能不能把空间复杂度再压缩一层？
  • 有没有另一种常见模板也能解决这题？

Copy List with Random Pointer

这个题型 / 算法点的总结

Copy List with Random Pointer 主要在练链表指针操作，重点是想清楚节点之间该怎么断开、反转和接回去。

题目含义

这题难点在于除了 next 之外还有 random 指针。
最稳的写法是：

  1. 第一遍创建所有新节点，建立 旧节点 -> 新节点 的映射
  2. 第二遍连接 next 和 random

代表 Python 代码

from typing import Optional

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        old_to_new = {}
        cur = head

        while cur:
            old_to_new[cur] = Node(cur.val)
            cur = cur.next

        cur = head
        while cur:
            old_to_new[cur].next = old_to_new.get(cur.next)
            old_to_new[cur].random = old_to_new.get(cur.random)
            cur = cur.next

        return old_to_new[head]

时间复杂度

O(n)。

空间复杂度

O(n)。

怎么想到这个方法

先看题型识别里的信号：这题本质上就是 哈希映射复制 / Hash Map Copy。把题目翻译成这个模板后，再去套对应的不变量、状态定义或数据结构，就会更容易写出来。

示例 case

  • 输入：链表节点除 next 外还有 random 指针
  • 输出：一条深拷贝链表，next 和 random 关系都要复制。

常见 Follow-up

  • 如果空间受限，能不能改成排序或双指针？
  • 如果要返回所有答案而不是一个答案，如何去重？
Cassie Liang · Study Notes GitHub