第 09 站 · 链表与树

链表与指针

反转链表 + 快慢指针时间 O(n) · 空间 O(1)

周赛难度分难度分 1232–难度分 1782· 中位难度分 1507（2/27 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 09 站 · 27 题

先学: 原地数组
学完去: 树的遍历
缓存索引
面试频次: 7 家公司考过 · 面经出现 11 次LinkedIn 3、Microsoft 3、Amazon 1、Arista 1、HubSpot 1

先做这道

LC 203移除链表元素简单

卡住再看

用哑节点统一删除头节点与普通节点，维护前驱指针。

要点

改指针之前先存下 next。反转只有三步：存 next、指回前驱、整体前移。
头结点可能被删除或替换时，先建一个哑结点 dummy 指向 head，最后返回 dummy.next。
快指针一次两步、慢指针一次一步，用来找中点和判环；找倒数第 k 个结点则让前指针先走 k 步，再和后指针同速前进。

易错点

先改了 head.next 再去取 next，后面的链表就丢了。
访问 fast.next.next 之前要确认 fast 和 fast.next 都不为空。
把链表拆成两段后忘了把前半段的尾部置空，合并或遍历时会成环。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

链表 · 改指针完成插入、删除、反转

链表 1 → 2 → 3 → 4：在位置 2 插入 9，删除位置 0，再反转

换个输入

当前处理已发现 / 已计算答案

从 head 读: 1 → 2 → 3 → 4

每个结点存一个值和指向下一个结点的指针。从 head 出发只能一个一个往后走。

速度

步骤 1 / 18

始终成立改一根指针之前，先保存它原来指向的结点，链表就不会断。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 203。

Python

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


def reverse(head):
    prev = None
    while head:
        nxt = head.next  # save it before rewiring
        head.next = prev
        prev, head = head, nxt
    return prev


def middle(head):
    """Middle node; the second of the two middles for even lengths."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

C++

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v, ListNode* n = nullptr) : val(v), next(n) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* nxt = head->next;  // save it before rewiring
        head->next = prev;
        prev = head;
        head = nxt;
    }
    return prev;
}

// Middle node; the second of the two middles for even lengths.
ListNode* middle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode nxt = head.next; // save it before rewiring
            head.next = prev;
            prev = head;
            head = nxt;
        }
        return prev;
    }

    // Middle node; the second of the two middles for even lengths.
    ListNode middle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverse(head *ListNode) *ListNode {
	var prev *ListNode
	for head != nil {
		next := head.Next // save it before rewiring
		head.Next = prev
		prev, head = head, next
	}
	return prev
}

// middle returns the middle node; the second of the two middles for even lengths.
func middle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
	}
	return slow
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

哑结点 + 尾指针拼接新链表时间 O(m + n) · 空间 O(1)

要边走边拼出一条新链表（合并、分区、两数相加、删除）：先放一个哑结点，尾指针 tail 只往后接，头结点就不用特判，最后返回 dummy.next。LC 21 合并两个有序链表、LC 2 两数相加、LC 86 分隔链表都是这个形状。

Python

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


def merge_two(a, b):
    """One sorted list from two, reusing their nodes."""
    dummy = tail = ListNode()  # a placeholder head: the first node needs no special case
    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  # whatever is left is sorted already
    return dummy.next

C++

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v, ListNode* n = nullptr) : val(v), next(n) {}
};

// One sorted list from two, reusing their nodes.
ListNode* mergeTwo(ListNode* a, ListNode* b) {
    ListNode dummy(0);  // a placeholder head: the first node needs no special case
    ListNode* tail = &dummy;
    while (a && b) {
        ListNode*& smaller = a->val <= b->val ? a : b;
        tail->next = smaller;
        smaller = smaller->next;
        tail = tail->next;
    }
    tail->next = a ? a : b;  // whatever is left is sorted already
    return dummy.next;
}

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // One sorted list from two, reusing their nodes.
    ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0, null), tail = dummy; // the first node needs no special case
        while (a != null && b != null) {
            if (a.val <= b.val) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }
        tail.next = a != null ? a : b; // whatever is left is sorted already
        return dummy.next;
    }
}

type ListNode struct {
	Val  int
	Next *ListNode
}

// mergeTwo returns one sorted list from two, reusing their nodes.
func mergeTwo(a, b *ListNode) *ListNode {
	dummy := &ListNode{} // a placeholder head: the first node needs no special case
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil { // whatever is left is sorted already
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

按 k 个一组反转时间 O(n) · 空间 O(1)

只反转链表的一段或一组一组地反转：prev 停在这一组前面，先数够 k 个（不够就保持原样），在组内原地反转，再把组头组尾接回去，prev 移到这组的新尾巴。LC 25 K 个一组翻转链表、LC 24 两两交换（k = 2）、LC 92 反转链表 II 都是这个骨架。

Python

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


def reverse_k_group(head, k: int):
    """Reverses every full group of k nodes; a shorter tail stays as it is (LC 25)."""
    dummy = ListNode(0, head)
    prev = dummy  # the node before the group being reversed
    while True:
        tail = prev
        for _ in range(k):  # is there a full group after prev?
            tail = tail.next
            if not tail:
                return dummy.next
        nxt, cur, p = tail.next, prev.next, tail.next
        while cur is not nxt:  # reverse prev.next..tail, hanging it onto nxt
            cur.next, p, cur = p, cur, cur.next
        first = prev.next  # the group's old first node is now its last
        prev.next = tail
        prev = first

C++

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v, ListNode* n = nullptr) : val(v), next(n) {}
};

// Reverses every full group of k nodes; a shorter tail stays as it is (LC 25).
ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;  // the node before the group being reversed
    while (true) {
        ListNode* tail = prev;
        for (int i = 0; i < k; i++) {  // is there a full group after prev?
            tail = tail->next;
            if (!tail) return dummy.next;
        }
        ListNode *nxt = tail->next, *cur = prev->next, *p = nxt;
        while (cur != nxt) {  // reverse prev->next..tail, hanging it onto nxt
            ListNode* after = cur->next;
            cur->next = p;
            p = cur;
            cur = after;
        }
        ListNode* first = prev->next;  // the group's old first node is now its last
        prev->next = tail;
        prev = first;
    }
}

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Reverses every full group of k nodes; a shorter tail stays as it is (LC 25).
    ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy; // the node before the group being reversed
        while (true) {
            ListNode tail = prev;
            for (int i = 0; i < k; i++) { // is there a full group after prev?
                tail = tail.next;
                if (tail == null) return dummy.next;
            }
            ListNode nxt = tail.next, cur = prev.next, p = nxt;
            while (cur != nxt) { // reverse prev.next..tail, hanging it onto nxt
                ListNode after = cur.next;
                cur.next = p;
                p = cur;
                cur = after;
            }
            ListNode first = prev.next; // the group's old first node is now its last
            prev.next = tail;
            prev = first;
        }
    }
}

type ListNode struct {
	Val  int
	Next *ListNode
}

// reverseKGroup reverses every full group of k nodes; a shorter tail stays as it is (LC 25).
func reverseKGroup(head *ListNode, k int) *ListNode {
	dummy := &ListNode{0, head}
	prev := dummy // the node before the group being reversed
	for {
		tail := prev
		for i := 0; i < k; i++ { // is there a full group after prev?
			tail = tail.Next
			if tail == nil {
				return dummy.Next
			}
		}
		next, cur, p := tail.Next, prev.Next, tail.Next
		for cur != next { // reverse prev.Next..tail, hanging it onto next
			cur.Next, p, cur = p, cur, cur.Next
		}
		first := prev.Next // the group's old first node is now its last
		prev.Next = tail
		prev = first
	}
}

为什么对

反转的不变式：prev 是已反转部分的头，cur 是未处理部分的头，两段互不相连。每步先存 cur.next，再让 cur 指向 prev，然后一起前进，不变式保持；cur 为空时 prev 就是新头。
快慢指针判环：两者都进环后，快指针每步多走一格，距离每步减一（按环长取模），所以一圈之内必然相遇；无环时快指针先走到空。
哑节点让「删头节点」和「删中间节点」变成同一种操作：每个真实节点都有前驱，不需要特判。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

链表题我先想清楚指针改动的顺序。反转时维护 prev 和 cur：先存下 cur.next，再把 cur 指回 prev，然后两个指针一起前进，cur 为空时 prev 就是新头。可能删头或换头时加一个哑节点，所有真实节点都有前驱，省掉特判。判环或找中点用快慢指针，进环后快指针每步追近一格，一定会相遇。都是 O(n) 时间、O(1) 空间。

English

For linked lists I first fix the order of pointer changes. To reverse, I keep prev and cur: save cur.next, point cur back at prev, then advance both, and when cur is null prev is the new head. When the head might change I add a dummy node so every real node has a predecessor. For cycles and midpoints I use fast and slow pointers, and inside a cycle the fast one closes the gap by one node per step, so they must meet.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）

反转的不变式：prev 是已反转部分的头，cur 是未处理部分的头，两段互不相连。每步先存 cur.next，再让 cur 指向 prev，然后一起前进，不变式保持；cur 为空时 prev 就是新头。
快慢指针判环：两者都进环后，快指针每步多走一格，距离每步减一（按环长取模），所以一圈之内必然相遇；无环时快指针先走到空。
哑节点让「删头节点」和「删中间节点」变成同一种操作：每个真实节点都有前驱，不需要特判。

小测

4 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。去 OA 选择题练习

4 道题

Floyd 判圈算法（慢指针一次一步，快指针一次两步）中，两个指针在环里相遇后，怎样找到环的入口？
- 相遇点就是入口
- 把一个指针放回头节点，两个指针都改成一次一步，再次相遇的位置就是入口
- 先数出环长，再在链表上二分查找
- 快指针继续一次两步，直到回到头节点
一个同时保存 head 和 tail 指针的单链表，下面哪个操作不是 O(1)？
- 删除尾节点
- 在尾部插入
- 在头部插入
- 删除头节点
链表题里常在头节点前加一个哑节点（dummy），它主要解决什么问题？
- 让链表可以 O(1) 随机访问
- 减少内存占用
- 让单链表可以反向遍历
- 头节点可能被删除或替换时，不用单独处理「改 head」这种特殊情况

链表有 n 个节点。suffix_lengths 的时间复杂度是？

def length(node):
    n = 0
    while node:
        n += 1
        node = node.next
    return n

def suffix_lengths(head):
    out = []
    while head:
        out.append(length(head))
        head = head.next
    return out

O(n)
O(n log n)
O(2^n)
O(n²)

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

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

    return slow

分档练习

本站在 500 路里的 27 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

基础 6

#	题目	一句话思路	难度分
203	移除链表元素	用哑节点统一删除头节点与普通节点，维护前驱指针。
206	反转链表	迭代反转链表，练习修改指针前保存后继。
21	合并两个有序链表	合并两条有序链表，处理空链和剩余尾段。
876	链表的中间结点	快慢指针定位中点，区分奇偶长度的终止条件。	难度分 1232
83	删除排序链表中的重复元素	利用有序性原地去重，保持保留节点之间的连接。
141	环形链表	快慢指针判断环，理解相遇而非走到末尾的终止条件。

核心 16

#	题目	一句话思路
160	相交链表	双指针换头消除长度差，依据节点身份判断相交。
19	删除链表的倒数第 N 个结点	固定间隔双指针删除倒数第n个节点，覆盖删除头节点。
82	删除排序链表中的重复元素 II	删除所有重复值而非只保留一个，维护连续重复区间的前驱。
328	奇偶链表	按位置奇偶拆成两条链再连接，防止尾部形成环。
86	分隔链表	稳定划分链表，保持两侧内部顺序并正确断开旧连接。
24	两两交换链表中的节点	局部两节点交换，练习前驱、当前组和后继的完整重连。
92	反转链表 II	只反转指定区间，处理反转段与前后部分的衔接。
61	旋转链表	将旋转转化为闭环后断链，处理k超过链长的情况。
142	环形链表 II	从快慢指针相遇点推导入环点，练习环距离关系。
234	回文链表	结合找中点与反转后半段判断回文，并考虑恢复输入结构。
143	重排链表	组合中点定位、反转与交替合并，避免丢失未处理节点。
2	两数相加	逐位模拟加法，统一不同长度和最后进位。
445	两数相加 II	用栈处理高位在前的链表加法，避免依赖修改原链表。
138	随机链表的复制	复制随机指针链表，理解节点映射与原对象身份。
147	对链表进行插入排序	在链表上实现插入排序，维护已排序区间与插入位置。
708	循环有序列表的插入 🔒	在有序循环链表中定位插入位置，处理最大值到最小值的断点及全等节点。

进阶 5

#	题目	一句话思路	难度分
430	扁平化多级双向链表	展开多级双向链表，维护next、prev、child与回接位置。
148	排序链表	链表归并排序，练习断链、合并及O(n log n)复杂度。
23	合并 K 个升序链表	最小堆或分治合并多条有序链，分析总节点数和链数的影响。
25	K 个一组翻转链表	按k个节点分组反转，不足一组时保持原样，维护组边界。
1171	从链表中删去总和值为零的连续节点	将前缀和用于链表区间删除，通过相同前缀定位总和为零的连续节点。	难度分 1782

本站 OA 真题 4

Remove Even-Value Nodes from Linked ListIBM
Binary Linked List to DecimalCisco
Delete Nodes Greater Than XCisco
Implement an LRU CacheGeico

全部 4 道

Core Skills

不调库，亲手实现这一站用到的数据结构或算法，四种语言都能判题。

单链表简单