链表

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)$ 空间 ...