0 Linked List Basic

链表是什么？

链表是一种通过指针将节点串联起来的线性数据结构。每个节点包含数据和指向下一个节点的指针

 head
  ↓
 [1] → [2] → [3] → [4] → None

与数组的对比：

操作	数组	链表
按下标访问	O(1)	O(n)
头部插入/删除	O(n)	O(1)
中间插入/删除（已知位置）	O(n)	O(1)
空间	连续内存	分散内存

Python 中的链表节点

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next

链表的核心操作

 1# 遍历
 2cur = head
 3while cur:
 4    print(cur.val)
 5    cur = cur.next
 6
 7# 在 node 后面插入 new_node
 8new_node.next = node.next
 9node.next = new_node
10
11# 删除 node 的下一个节点
12node.next = node.next.next

链表题的三大神器

哑节点（Dummy Node）：在链表头部加一个虚拟节点，避免处理"头节点可能被删除/改变"的特殊情况

1dummy = ListNode(0)
2dummy.next = head
3# ... 操作 ...
4return dummy.next  # 新的头节点

快慢指针：两个指针以不同速度遍历链表

 1# 找链表中点（慢指针走一步，快指针走两步）
 2slow = fast = head
 3while fast and fast.next:
 4    slow = slow.next
 5    fast = fast.next.next
 6# slow 现在指向中点（偶数个节点时是中间偏左）
 7
 8# 检测环
 9slow = fast = head
10while fast and fast.next:
11    slow = slow.next
12    fast = fast.next.next
13    if slow == fast:
14        return True  # 有环

递归：链表天然适合递归，处理当前节点 + 递归处理剩余链表。

1def process(node):
2    if not node:
3        return None  # base case
4    # 递归处理剩余部分
5    node.next = process(node.next)
6    # 处理当前节点
7    return node

1 快慢指针系

1.1 环形链表 | Easy

题目：给链表头节点 head,判断链表中是否有环。要求 $O(1)$ 空间

思路分析：

Floyd判圈（龟兔赛跑）：slow每跑一步，fast每次跑两步

无环：fast先到达None，退出循环
有环：两者分先后进入环，进入环后两者相对速度不同必然相遇朴素方法：哈希表或者集合set存访问过的节点，空间复杂度为O(n)

踩坑记录：

循环条件：因为 fast 每次要走两步 fast.next.next,必须保证这两步的访问都不会在空指针上出错:

fast 非空 → 才能安全访问 fast.next
fast.next 非空 → 才能安全访问 fast.next.next

代码：

 1# Definition for singly-linked list.
 2class ListNode:
 3    def __init__(self, x):
 4        self.val = x
 5        self.next = None
 6
 7# 快慢指针
 8class Solution:
 9    def hasCycle(self, head: Optional[ListNode]) -> bool:
10        slow = fast = head
11
12        while fast and fast.next:
13            slow = slow.next
14            fast = fast.next.next
15            if slow is fast:
16                return True
17        
18        return False
19
20# 集合版
21class Solution:
22    def hasCycle(self, head: Optional[ListNode]) -> bool:
23        seen = ()
24
25        dummy = head
26        while dummy:
27            if dummy not in seen:
28                seen.add(dummy)
29                dummy = dummy.next
30            else:
31                return True
32        
33        return False

复杂度：

时间:$O(n)$ ，slow 入环后最多再走一圈就被追上
空间:$O(1)$

1.2 环形链表 II | Medium

题目: 返回入环的第一个节点，无环返回 null。要求 $O(1)$ 空间

思路分析：

设：头到环入口距离为a，入口到相遇点距离为b，相遇点沿环回到入口距离是c，环长是$L = b + c$ 相遇时： $$\text{slow走了a + b，}\quad \text{fast走了a + b + kL}$$ 由于fast速度时slow的两倍： $$a + b + kL = 2(a + b) \Rightarrow a + b = kL \Rightarrow a = kL - b = (k - 1)b + c$$ 结论： $$a = (k - 1)L + c$$ 也就是说：从头节点和从相遇点同时同速度出发，前者走a步到入口时，后者走了$(k - 1)L$整圈+c步，也恰好在环入口，两指针第一次相遇的地方就是环入口

踩坑记录：

为什么slow和fast相遇时slow一定只走了一圈呢？

设 slow 走了 a 步刚到环入口。此时 fast 已经走了 2a 步,一定在环内的某个位置。
设此刻 fast 落后 slow 的距离(沿行进方向从 fast 追到 slow 需要的步数)为 g。由于两者都在环上,有: $0 \le g \le L - 1$，所以 slow 在环内走的距离不足一圈,相遇必然发生在 slow 的第一圈内。

代码：

 1class Solution:
 2    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
 3        slow = fast = head
 4
 5        while fast and fast.next:
 6            slow = slow.next
 7            fast = fast.next.next
 8            if slow is fast:
 9                p = head
10                while p is not slow:
11                    slow = slow.next
12                    p = p.next
13                return p
14        
15        return None

复杂度：

时间:$O(n)$ 第一阶段 $O(n)$,第二阶段最多再走 $a < n$ 步
空间:$O(1)$

1.3 删除链表的倒数第 N 个结点 | Meidum

题目: 删除链表的倒数第 n 个结点,返回头节点。进阶:一趟扫描。

思路分析：

单链表不能回头,“倒数第 n"要转成"正数”:让 fast 先走 n 步,然后 fast、slow 同速前进。当 fast 到达末尾 None 时,fast 与 slow 恒定相距 n,slow 正好在倒数第 n 个。
删除需要前驱, 所以两个指针都从 dummy 出发, 并让 fast 先走 n+1 步或fast 从 head 出发先走 n 步, slow 从 dummy 出发到达倒数n + 1个
为什么必须 dummy:当删的是头节点(如链表长度恰为 n)时,没有 dummy 就没有前驱可操作,得单独特判。 ![[lc19.png]]

踩坑记录：

删除动作是 slow.next = slow.next.next,别手滑写成 slow = slow.next.next(那是移动指针不是删除)
fast = dummy: n + 1. fast = head: n 代码：

 1class Solution:
 2    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
 3        dummy = ListNode(0, head)
 4        slow = fast = dummy
 5
 6        for _ in range(n + 1):
 7            fast = fast.next
 8        
 9        while fast:
10            fast = fast.next
11            slow = slow.next
12        slow.next = slow.next.next
13
14        return dummy.next

复杂度：

时间:$O(L)$,一趟
空间:$O(1)$

1.4 回文链表 | Easy

题目: 给单链表头节点 head,判断是否为回文链表。进阶要求:$O(n)$ 时间 + $O(1)$ 空间。

思路分析：

快慢指针找中点:循环结束后 slow 停在中点(奇数)或下中位(偶数)
反转后半段:从 slow 开始反转
双指针比较:一个从 head、一个从反转后的后半头,逐个比 val
再反转回去,恢复原链表结构

关键观察:奇数长度时中间节点归属哪半边不影响结果，比较循环以较短的后半段走完为终止条件,中间那个节点天然被跳过

1 → 2 → 3 → 2 → 1
        ↑ slow(中点)
反转后半: 1 → 2 → 3   
前半从 1 走,后半从 1 走,比较 2 次即结束,3 不参与

踩坑记录：

比较的是val，而不是节点本身

代码：

 1class Solution:
 2    def isPalindrome(self, head: Optional[ListNode]) -> bool:
 3        # 快慢指针找中点
 4        slow = fast = head
 5        while fast and fast.next:
 6            slow = slow.next
 7            fast = fast.next.next
 8        
 9        # 反转后半部分
10        pre, cur = None, slow
11        while cur:
12            next = cur.next
13            cur.next = pre
14            pre, cur = cur, next
15
16        # 双指针比较
17        first, second = head, pre
18        while second:
19            if first.val != second.val:
20                return False
21            first = first.next
22            second = second.next
23        
24        return True

复杂度：

时间:$O(n)$ 找中点 $n/2$ + 反转 $n/2$ + 比较 $n/2$
空间:$O(1)$

2 反转系

2.1 反转链表 | Easy

题目: 给单链表头节点 head,反转链表并返回新的头节点。

思路分析：

方法一：迭代三指针 ![[lc206.png]] 维护 pre(已反转部分的头)和 cur(待处理节点)。每一步:

先存 nxt = cur.next(存后路,否则断链后找不到了)
掉头 cur.next = pre
双指针整体右移:pre = cur, cur = nxt 循环结束时 cur is None,pre 就是新头

方法二：递归 假设 reverseList(head.next) 已经把后面全部反转好了,返回新头 new_head。此时 head.next 指向的是反转后子链的尾巴,所以:

1head.next.next = head   # 让尾巴指回自己
2head.next = None        # 自己变成新尾巴

踩坑记录：想清楚返回值是什么

代码：

1# 迭代
2class Solution:
3    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
4        pre, cur = None, head
5        while cur:
6            next = cur.next
7            cur.next = pre
8            pre, cur = cur, next
9        return pre

1# 递归
2class Solution:
3    def reverseList(self, head: ListNode) -> ListNode:
4        if head is None or head.next is None:
5            return head
6        new_head = self.reverseList(head.next)
7        head.next.next = head
8        head.next = None
9        return new_head

复杂度：

解法	时间	空间
迭代	$O(n)$	$O(1)$
递归	$O(n)$	$O(n)$(递归栈深度)

2.2 两两交换链表中的节点 | Medium

题目：两两交换相邻节点并返回新头(必须交换节点,不能只改 val)

思路分析：

每一组涉及三个角色:前驱 pre、第一个节点 a、第二个节点 b。一组交换固定三步:

pre → a → b → rest        目标: pre → b → a → rest
1. pre.next = b
2. a.next = b.next
3. b.next = a

踩坑记录：

三步交换顺序
移动完一组后pre的位置

代码：

 1# 迭代
 2class Solution:
 3    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
 4        dummy = List(0, head)
 5        pre = dummy
 6
 7        while pre.next and pre.next.next:
 8            a, b = pre.next, pre.next.next
 9            pre.next = b
10            a.next, b.next = b.next, a
11            pre = a
12        
13        return dummy.next

1# 递归
2class Solution:
3    def swapPairs(self, head: ListNode) -> ListNode:
4        if not head or not head.next:
5            return head
6        a, b = head, head.next
7        a.next = self.swapPairs(b.next)
8        b.next = a
9        return b

复杂度：

解法	时间	空间
迭代	$O(n)$	$O(1)$
递归	$O(n)$	$O(n)$

3 模拟系

3.1 两数相加 | Medium

题目: 两个非空链表表示两个非负整数,逆序存储(个位在表头),每个节点存一位数字。返回表示两数之和的链表。

思路分析：

逆序存储恰好是竖式加法的方向:从个位开始加,进位往后传：

每一位:s = (l1?.val) + (l2?.val) + carry,当前位 s % 10,新进位 s // 10
两条链长度可能不同,某条走完后按 0 处理
最后可能还剩一个进位(如 5+5=10),必须补一个节点

踩坑记录：

漏最后的进位:[5] + [5] 应得 [0,1]，用 l1 or l2 or carry 作循环条件就天然覆盖

代码：

 1class Solution:
 2    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
 3        dummy = ListNode()
 4        tail = dummy
 5        carry = 0
 6
 7        while l1 or l2 or carry:
 8            s = carry
 9            if l1:
10                s += l1.val
11                l1 = l1.next
12            if l2:
13                s += l2.val
14                l2 = l2.next
15            carry, digit = s // 10, s % 10
16            tail.next = ListNode(digit)
17            tail = tail.next
18        
19        return dummy.next

复杂度：

时间:$O(\max(m, n))$
空间:$O(1)$(不计输出链表;计输出则 $O(\max(m,n))$)

3.2 相交链表 | Easy

题目: 给两个单链表的头节点 headA 和 headB,找出并返回两个链表相交的起始节点;不相交返回 null。要求 $O(1)$ 空间。注意:相交指的是节点引用相同(同一块内存),不是 val 相等。相交后两条链表完全重合(单链表每个节点只有一个 next,分不了叉)。

思路分析：设 A 独有部分长 $a$,B 独有部分长 $b$,公共部分长 $c$ 让指针 pA 走完 A 再走 B,pB 走完 B 再走 A: $$a + c + b = b + c + a$$ 两个指针走的总路程相等,所以必然同时到达相交点(有交点时),或同时到达 None(无交点时)。一句话:走到尽头就换路,两条路加起来一样长,错开的步差被抹平了

pA: a → c → b → [交点]
pB: b → c → a → [交点]

踩坑记录：

换路时机
比较节点不是节点val

代码：

1class Solution:
2    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
3        pa, pb = headA, headB
4        while pa is not pb:
5            pa = pa.next if pa else headB
6            pb = pb.next if pb else headA
7        return pa

复杂度：

时间:$O(m+n)$,每个指针最多把两条链各走一遍
空间:$O(1)$

4 组合结构系

4.1 随机链表的复制 | Medium

题目: 链表节点多一个 random 指针,可指向任意节点或 null。对链表做深拷贝

1class Node:
2    def __init__(self, x, next=None, random=None):
3        self.val = x
4        self.next = next
5        self.random = random

思路分析：

复制到某个节点时,它的 random指向的节点可能还没被创建。核心是建立"原节点 → 新节点"的映射

方法一：哈希表

1st round：只建立节点mp[old] = Node(old.val)
2nd round：连线 mp[old].random = mp.get(old.random, None)

踩坑记录：深拷贝意味着新链的任何指针都不能指向原链节点

代码：

 1# 哈希表
 2class Solution:
 3    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
 4        if not head:
 5            return head
 6        
 7        mp = {}
 8        cur = head
 9        while cur:
10            mp[cur] = Node(cur.val)
11            cur = cur.next
12        cur = head
13        while cur:
14            mp[cur].next = mp.get(cur.next)
15            mp[cur].random = mp.get(cur.random)
16            cur = cur.next
17        
18        return mp[head]

方法二：交织法 O(1)

把映射编码进链表结构本身,三趟:

交织:每个原节点后面插入它的拷贝:A → A' → B → B' → ...,此时 old.next 就是它的拷贝(结构即哈希)
连 random:old.next.random = old.random.next(若 old.random 非空)
拆分:把两条链拆开,必须恢复原链表

踩坑记录：

random 为 None:old.random.next 之前必须判 old.random 非空;哈希版用 mp.get() 规避

代码:

 1class Solution:
 2    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
 3        if not head:
 4            return head
 5        
 6        cur = head
 7        while cur:
 8            cur.next = Node(cur.val, cur.next)
 9            cur = cur.next.next
10        
11        cur = head
12        while cur:
13            if cur.random:
14                cur.next.random = cur.random.next
15            cur = cur.next.next
16        
17        cur, new_head = head, head.next
18        while cur:
19            copy = cur.next
20            cur.next = copy.next
21            copy.next = copy.next.next if copy.next else None
22            cur = cur.next
23        
24        return new_head

复杂度：

解法	时间	空间
哈希表	$O(n)$	$O(n)$
交织法	$O(n)$	$O(1)$(不计输出)

4.2 LRU 缓存 | Medium

题目：设计满足 LRU(最近最少使用)约束的缓存,get 和 put 均要求 $O(1)$ 平均时间:

get(key):存在则返回值,否则返回 -1
put(key, value):插入或更新;超容量时逐出最久未使用的键
两个操作都算"使用",要刷新新鲜度

思路分析：

$O(1)$ 的两个需求拆开看:

按 key 定位 → 哈希表
维护"使用顺序"且任意位置 $O(1)$ 删除、头部 $O(1)$ 插入 → 双向链表(单链表删除拿不到前驱,做不到 $O(1)$) 组合:哈希表的 value 直接存链表节点。约定链表头 = 最新,尾 = 最旧。
get:哈希查到节点 → 摘下 → 插回头部 → 返回值
put:已存在则更新值并提到头部;不存在则建节点插头部,超容量时删尾节点,并同步删哈希表里对应的 key(所以节点里必须存 key,不然删尾时不知道删哈希的哪一项) 工程实现只需两个私有原语:_remove(node) 和 _add_front(node),所有操作由它俩组合而成。再加头尾哨兵节点,_remove/_add_front 就完全没有空指针分支。

踩坑记录：

写原语操作
先插入再逐出
元组赋值不是"同时发生"：右边先整体求值成一个元组，左边的赋值目标从左到右依次执行

代码：

 1class DNode:
 2    __slots__ = ("key", "val", "prev", "next")
 3    def __init__(self, key=0, val=0):
 4        self.key, self.val = key, val
 5        self.prev = self.next = None
 6
 7
 8class LRUCache:
 9
10    def __init__(self, capacity: int):
11        self.cap = capacity
12        self.mp = {}
13        self.head, self.tail = DNode(), DNode()
14        self.head.next, self.tail.prev = self.tail, self.head
15
16    def _remove(self, node: DNode) -> None:
17        node.prev.next, node.next.prev = node.next, node.prev
18
19    def _add_front(self, node: DNode) -> None:
20        node.next, node.prev = self.head.next, self.head
21        self.head.next.prev = node
22        self.head.next = node
23
24    def get(self, key: int) -> int:
25        if key not in self.mp:
26            return -1
27        node = self.mp[key]
28        self._remove(node)
29        self._add_front(node)
30        return node.val
31
32    def put(self, key: int, value: int) -> None:
33        if key in self.mp:
34            node = self.mp[key]
35            self._remove(node)
36            node.val = value
37            self._add_front(node)
38            return 
39        node = DNode(key, value)
40        self.mp[key] = node
41        self._add_front(node)
42        if len(self.mp) > self.cap:
43            oldnode = self.tail.prev
44            self._remove(oldnode)
45            del self.mp[oldnode.key]

复杂度：

时间:get / put 均摊 $O(1)$
空间:$O(\text{capacity})$

5 归并系

5.1 合并两个有序链表 | Easy

题目：将两个升序链表 list1、list2 合并为一个新的升序链表并返回。新链表由原链表节点拼接而成(不新建节点)

思路分析：新链表的头是 list1 还是 list2 开头不确定,挂一个 dummy,用 tail 指针在后面不断接较小的节点。谁被接走,谁的指针就前移。循环结束后,还没走完的那条链整条接到 tail 后面(它本身有序,不用逐个接)

踩坑记录：

比较用 <= 而不是 <,相等时取 list1,保证归并稳定

代码：

 1class Solution:
 2    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
 3        dummy = ListNode()
 4        tail = dummy
 5
 6        while list1 and list2:
 7            if list1.val <= list2.val:
 8                tail.next = list1
 9                list1 = list1.next
10            else:
11                tail.next = list2
12                list2 = list2.next
13            tail = tail.next
14        tail.next = list1 or list2
15
16        return dummy.next

 1# 递归
 2class Solution:
 3    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
 4        if not list1: 
 5	        return list2
 6        if not list2: 
 7	        return list1
 8        if list1.val <= list2.val:
 9            list1.next = self.mergeTwoLists(list1.next, list2)
10            return list1
11        else:
12            list2.next = self.mergeTwoLists(list1, list2.next)
13            return list2

复杂度：

解法	时间	空间
迭代	$O(m+n)$	$O(1)$
递归	$O(m+n)$	$O(m+n)$(栈深)

5.2 排序链表 | Medium

题目: 对链表按升序排序。进阶:$O(n \log n)$ 时间、常数级空间

思路分析：

找中点断链:快慢指针,断开成两半
递归排序两半
合并:直接调 5.1 题的 merge

找中点用 slow, fast = head, head.next 的起点(fast 先一步),保证偶数长度时 slow 停在上中位,slow.next 断开后两半是 $\lceil n/2 \rceil / \lfloor n/2 \rfloor$

踩坑记录：

中点起手式用错
忘记断链:mid = slow.next; slow.next = None 的第二句漏掉,递归收不敛直接 RE。链表归并和数组归并最大的差异就在"必须物理断开"

代码：

 1class Solution:
 2    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
 3        if not head or not head.next:
 4            return head
 5        
 6        slow, fast = head, head.next
 7        while fast and fast.next:
 8            slow = slow.next
 9            fast = fast.next.next
10        mid, slow.next = slow.next, None
11        # 递归排序
12        left, right = self.sortList(head), self.sortList(mid)
13        # 合并
14        dummy = tail = ListNode()
15        while left and right:
16            if left.val <= right.val:
17                tail.next = left
18                left = left.next
19            else:
20                tail.next = right
21                right = right.next
22            tail = tail.next
23        tail.next = left or right
24
25        return dummy.next

复杂度：

时间:$O(n \log n)$， $\log n$ 层,每层合并共 $O(n)$
空间:$O(\log n)$，递归栈(自底向上版为 $O(1)$)

0 Linked List Basic#

1 快慢指针系#

2 反转系#

3 模拟系#

4 组合结构系#

5 归并系#

0 Linked List Basic

1 快慢指针系

2 反转系

3 模拟系

4 组合结构系

5 归并系