链表
一、什么是链表
链表由一系列节点（node）组成。每个节点至少包含两部分：数据域（存值）和指针域（存「下一个节点」的地址）。多个节点通过指针首尾相接，形成一条「链」。链表的头一般用一个头指针记录；最后一个节点的「下一个」指向空（null），表示链结束。
和数组不同，链表在内存里不必连续：每个节点可以单独申请，只要记住「下一个」是谁就能顺序访问。因此在已知节点前/后插入或删除，只需改一两条指针，不需要像数组那样整体移动元素。
二、单向链表
单向链表的每个节点只有一个「后继」指针（常叫 next），从头部一路走到尾部。要访问第 i 个节点，必须从 head 开始走 i 步，所以按位置访问是 O(n)。
在 Python 中常用「节点类 + 可选类型」表示链表，头指针为第一个节点的引用或 None：
from typing import Optional
class ListNode:
"""单向链表节点：数据域 val，指针域 next。"""
def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None:
self.val = val
self.next = next
# 例：构造 3 -> 7 -> 2 -> None
head: Optional[ListNode] = ListNode(3, ListNode(7, ListNode(2)))三、双向链表
双向链表的每个节点有两个指针：next 指向后继，prev 指向前驱。这样从任意节点可以往前或往后走，在「已知节点」处做前插或删除也只需 O(1)。代价是多占一份指针空间，且维护时要同时改 prev 和 next，写代码要小心别漏改。
四、链表 vs 数组
选择用数组还是链表，取决于你更关心「随机访问」还是「动态插入删除」：
| 对比项 | 数组 | 链表 |
|---|---|---|
| 存储 | 连续 | 分散，靠指针连 |
| 按下标/位置访问 | O(1) | O(n) |
| 在头/已知节点处插入、删除 | O(n)（要移动） | O(1) |
| 在末尾追加 | O(1) 均摊 | O(1)（若维护尾指针） |
| 查找（未排序） | O(n) | O(n) |
| 额外空间 | 少 | 每节点多一/两个指针 |
需要频繁按位置访问、或需要二分查找时用数组（或基于数组的结构）；需要频繁在头部或中间插入删除、且不需要按位置随机访问时，链表更合适。
五、头节点与哨兵（dummy）
链表的头很特殊：没有「前一个节点」，所以在头部插入、删除时要单独处理，代码容易写乱。一种常用技巧是加一个哨兵节点（dummy）：一个不存有效数据的节点，其 next 指向真正的第一个节点。这样「在第一个节点前插入」就变成「在 dummy 后插入」，和中间插入逻辑统一，头删也变成「删 dummy 的后继」，代码更简洁、少判空。
def insert_at_head(head: Optional[ListNode], val: int) -> ListNode:
"""在链表头前插入新节点，返回新头。用 dummy 可避免对 head 为 None 的分支。"""
dummy: ListNode = ListNode(0, head)
dummy.next = ListNode(val, head)
return dummy.next # 新头六、链表操作的复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 按位置访问第 i 个 | O(n) | 从头走 i 步 |
| 在头前插入 / 删头 | O(1) | 改 head 或 dummy.next |
| 在已知节点后插入 | O(1) | 改两条 next |
| 删除已知节点的后继 | O(1) | 改一条 next |
| 双向：在已知节点前插入/删除自身 | O(1) | 改 prev、next |
| 查找值为 x 的节点 | O(n) | 顺序遍历 |
七、常见应用延伸
下面几类题能帮你巩固「改指针」的写法，并在面试和工程里常见。
1. 合并两个有序链表
给定两个按值升序的单链表，合并成一个升序链表。思路：类似归并两个有序数组，用两个指针分别指向两个链的当前节点，每次取较小的接到结果链后面。时间 O(n+m)，空间 O(1)。
2. 反转链表
把单向链表整体反转。迭代：维护 prev、cur，每次把 cur.next 改为 prev，再前进。时间 O(n)，空间 O(1)。
3. 找链表中点（快慢指针）
慢指针一步、快指针两步；快指针到尾部时慢指针在中点。常用于对半拆链、判断回文链表。时间 O(n)。
4. 判断环与环入口（Floyd 判环）
若链表有环，快慢指针一定会相遇，可先判环；再从 head 与相遇点各放一个指针同速走，相遇处即为环入口。时间 O(n)，空间 O(1)。详见下方例题。
5. LRU 缓存中的链表
LRU 可用哈希表 + 双向链表：哈希表 key→节点，双向链表按「最近使用」顺序（头最近、尾最久）。访问时把节点摘掉再插到头；满时删尾。查、更新、删均为 O(1)。
八、例题与代码详解
下面五道题分别对应合并、反转、找中点、判环与环入口，给出完整题目描述、Python3 解法（带类型标注）与详细讲解。节点定义同上：ListNode(val, next)。
例题 1：合并两个有序链表
题目描述：将两个按非递减顺序排列的单链表合并为一个非递减链表并返回新链表的头。新链表由原两链表的节点「拼接」而成（不改节点值，只改指针）。
输入：list1、list2 各自非递减，可能为空。
输出：合并后的链表头 Optional[ListNode]。
def merge_two_lists(
list1: Optional[ListNode],
list2: Optional[ListNode],
) -> Optional[ListNode]:
"""归并思路：dummy 哨兵，tail 指向当前结果链末尾，每次接上较小节点并后移。"""
dummy: ListNode = ListNode(0)
tail: ListNode = dummy
while list1 is not None and list2 is not None:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 if list1 is not None else list2
return dummy.next讲解：用 dummy 作为结果链的哨兵头，tail 始终指向当前结果链的最后一个节点。每次比较 list1.val 与 list2.val，将较小者接到 tail.next，并让 tail 和对应链的指针后移。当某一链走完后，把另一链剩余部分整体接到 tail.next。返回 dummy.next 即新头。时间 O(n+m)，空间 O(1)。
例题 2：反转链表
题目描述：给定单链表的头节点 head，请反转链表，并返回反转后的头节点。
输入：head 可能为 None（空链）或任意长度。
输出：反转后的链表头 Optional[ListNode]。
def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
"""迭代：维护 prev 与 cur，每次把 cur.next 指向前驱 prev，再一起前移。"""
prev: Optional[ListNode] = None
cur: Optional[ListNode] = head
while cur is not None:
nxt: Optional[ListNode] = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev讲解：prev 表示「已反转部分」的头，cur 表示当前待反转的节点。每次把 cur.next 改为 prev，这样当前节点就接在了已反转链的头部；然后 prev = cur、cur = nxt（事先保存 nxt = cur.next，否则会丢链）。当 cur 为 None 时，prev 即为新头。空链、单节点链自然成立。时间 O(n)，空间 O(1)。
例题 3：链表的中间节点（快慢指针）
题目描述：给定单链表的头节点 head，返回链表的中间节点。若有两个中间节点（长度为偶数），返回第二个中间节点。
输入：head 非空，节点数在 [1, 100]。
输出：中间节点的引用（不是值）。
def middle_node(head: Optional[ListNode]) -> Optional[ListNode]:
"""快慢指针：slow 一步，fast 两步；fast 到末尾时 slow 在中点（偶数时取第二个）。"""
slow: Optional[ListNode] = head
fast: Optional[ListNode] = head
while fast is not None and fast.next is not None:
slow = slow.next if slow else None
fast = fast.next.next
return slow讲解：slow 每次走 1 步，fast 每次走 2 步。当 fast 到达末尾（fast 为 None 或 fast.next 为 None）时，slow 恰好在中间。偶数长度时题目要求返回第二个中点，即「fast 多走一步再停」的约定下，当前写法正好返回第二个。时间 O(n)，空间 O(1)。该技巧可用于「对半拆链」「回文链表」等。
例题 4：环形链表 I（判断是否有环）
题目描述：给定单链表的头节点 head，判断链表中是否存在环。若存在某个节点的 next 再次指向链表中已经出现过的节点，则称链表有环。
输入：head 可能为 None；链中节点数 ≥ 0。
输出：有环返回 True，否则 False。要求 O(1) 额外空间时只能用快慢指针。
def has_cycle(head: Optional[ListNode]) -> bool:
"""Floyd 判环：快指针走两步、慢指针走一步，有环则必在环内相遇。"""
slow: Optional[ListNode] = head
fast: Optional[ListNode] = head
while fast is not None and fast.next is not None:
slow = slow.next if slow else None
fast = fast.next.next
if slow is fast:
return True
return False讲解：为什么有环时快慢一定会相遇？ 设进入环之前有 a 步，环长为 b。慢指针进入环时，快指针已在环内；之后把环展开成「模 b 的跑道」，慢指针每次 +1、快指针每次 +2，相当于快指针每轮相对慢指针多走 1 步。由于是模 b，最多 b 轮内快指针就会「套圈」追上慢指针，故一定相遇。无环时快指针会先到达 None，循环正常退出返回 False。时间 O(n)，空间 O(1)。
例题 5：环形链表 II（找环的入口）
题目描述：给定单链表的头节点 head，若链表有环，返回环的入口节点（即第一个被再次指向的节点）；若无环则返回 None。
输入：同例题 4。
输出：环入口节点引用，或无环时 None。
def detect_cycle_start(head: Optional[ListNode]) -> Optional[ListNode]:
"""先快慢指针相遇得到 meeting 点，再让 ptr1=head、ptr2=meeting 同速走，相遇处即环入口。"""
slow: Optional[ListNode] = head
fast: Optional[ListNode] = head
while fast is not None and fast.next is not None:
slow = slow.next if slow else None
fast = fast.next.next
if slow is fast:
break
else:
return None # 无环
ptr1: Optional[ListNode] = head
ptr2: Optional[ListNode] = slow
while ptr1 is not ptr2:
ptr1 = ptr1.next if ptr1 else None
ptr2 = ptr2.next if ptr2 else None
return ptr1讲解：为什么从 head 和相遇点同速走会在环入口相遇？ 设头到环入口长度为 a，环入口到相遇点长度为 c，环剩余部分为 b−c（环长 b）。快指针路程 = 2×慢指针路程，且快指针比慢指针多走了若干整圈，即 2(a+c) = a+c+k·b（k≥1），化简得 a = k·b−c = (k−1)·b + (b−c)。因此「从 head 走 a 步」和「从相遇点走 a 步」等价于「从相遇点走 (k−1) 圈再走 b−c」，两者都会到达环入口，故同速走一定在环入口相遇。先判环得到 slow/fast 相遇点，再用 ptr1=head、ptr2=meeting 同速前进直到相等即可。时间 O(n)，空间 O(1)。
九、小结
链表由节点通过指针串联而成，不要求连续存储。单向链表只有 next；双向链表有 prev 和 next。在已知节点处插入、删除是 O(1)，按位置访问是 O(n)。用哨兵可统一头部的插入删除。常见应用：合并两有序链、反转链表、快慢指针找中点/判环；LRU 可用「哈希表 + 双向链表」实现 O(1) 的访问与淘汰。下一章我们会学栈与队列——两种操作受限的线性结构，链表和数组都可以用来实现它们。