目标理解链表的内存模型掌握指针操作技巧熟练运用虚拟头节点、快慢指针、反转等核心模式解决复杂问题。一、为什么需要链表1.1 数组的结构性缺陷数组要求内存连续导致插入和删除的代价与数据规模成正比arr[1,2,3,4,5]# 头部操作O(n) —— 所有元素移动arr.insert(0,0)# [0, 1, 2, 3, 4, 5]arr.pop(0)# [1, 2, 3, 4, 5]# 中间操作O(n) —— 后半部分元素移动arr.insert(2,99)# [1, 2, 99, 3, 4, 5]核心矛盾数组的物理连续性带来了随机访问的优势O(1) 索引但也导致了动态修改的劣势。1.2 链表的解决思路链表通过指针连接离散节点将物理连续性要求转化为逻辑连续性数组连续内存 链表离散内存 ┌───┬───┬───┬───┐ ┌─────┐ ┌─────┐ ┌─────┐ │ 1 │ 2 │ 3 │ 4 │ │ 1 │●│────→│ 2 │●│────→│ 3 │●│────→ None └───┴───┴───┴───┘ └──┬──┘ └──┬──┘ └──┬──┘ 插入需批量移动 插入只需修改指针维度数组链表内存布局连续离散随机访问O(1)O(n)头部插入/删除O(n)O(1)中间插入/删除已知前驱O(n)O(1)缓存友好性高局部性低指针跳转选择策略查询频繁、修改稀少 →数组修改频繁、无需随机访问 →链表需要兼顾 →动态数组Python list或跳表二、单向链表从零实现2.1 节点定义链表的基本单元是节点包含数据域和指针域classListNode:链表节点def__init__(self,val0,nextNone):self.valval self.nextnextdef__repr__(self):returnstr(self.val)2.2 核心操作链表操作的本质是指针的重新指向。以下是最小可用实现classLinkedList:单向链表最小完整实现def__init__(self):self.headNoneself._size0defadd_at_head(self,val)-None:头插O(1)self.headListNode(val,self.head)self._size1defadd_at_tail(self,val)-None:尾插O(n) —— 需遍历到最后new_nodeListNode(val)ifnotself.head:self.headnew_nodeelse:currself.headwhilecurr.next:currcurr.nextcurr.nextnew_node self._size1defdelete_at_index(self,index:int)-None:删除第 index 个节点O(n)ifindex0orindexself._size:raiseIndexError(Index out of range)ifindex0:self.headself.head.nextelse:prevself.headfor_inrange(index-1):prevprev.nextprev.nextprev.next.next# 跳过目标节点self._size-1defto_list(self)-list:转换为 Python 列表result[]currself.headwhilecurr:result.append(curr.val)currcurr.nextreturnresult# 验证llLinkedList()ll.add_at_tail(1)ll.add_at_tail(2)ll.add_at_tail(3)ll.add_at_head(0)print(ll.to_list())# [0, 1, 2, 3]ll.delete_at_index(1)print(ll.to_list())# [0, 2, 3]三、链表算法的六大核心技巧3.1 技巧一虚拟头节点Dummy Head问题头节点没有前驱插入/删除时需要特殊处理。解决引入虚拟头节点统一所有位置的操作逻辑。defremove_elements(head:ListNode,val:int)-ListNode: 删除链表中所有值为 val 的节点 使用虚拟头节点避免对头节点的特殊判断 dummyListNode(0,head)# 虚拟头节点prevdummy currheadwhilecurr:ifcurr.valval:prev.nextcurr.next# 删除 currelse:prevcurr# prev 后移currcurr.nextreturndummy.next# 返回真正的头节点价值将头节点可能是目标的边界情况转化为普通情况代码更简洁bug 更少。3.2 技巧二反转链表三指针法迭代法用三个指针依次后移逐个反转指向。defreverse_list(head:ListNode)-ListNode: 反转单向链表 时间O(n)空间O(1) prevNonecurrheadwhilecurr:next_tempcurr.next# 暂存后继防止断链curr.nextprev# 反转指向prevcurr# prev 前移currnext_temp# curr 前移returnprev# 新的头节点执行过程1 → 2 → 3 → None步骤prevcurrnext_temp链表状态初始None121 → 2 → 3第1轮123None ← 12 → 3第2轮23NoneNone ← 1 ← 23第3轮3None—None ← 1 ← 2 ← 3递归法理解即可面试推荐迭代法defreverse_list_recursive(head:ListNode)-ListNode:递归反转ifnotheadornothead.next:returnhead new_headreverse_list_recursive(head.next)head.next.nexthead# 下一个节点指向自己head.nextNone# 断开原指向防止环returnnew_head3.3 技巧三快慢指针检测环Floyd 判圈算法defhas_cycle(head:ListNode)-bool: 判断链表是否有环 时间O(n)空间O(1) ifnotheadornothead.next:returnFalseslowhead fasthead.next# 快指针先走一步避免初始相遇whilefastandfast.next:ifslowfast:returnTrueslowslow.next# 慢1步fastfast.next.next# 快2步returnFalse原理有环时快指针相对慢指针的速度为 1 步/轮必然追上无环时快指针先到尾。找环入口defdetect_cycle(head:ListNode)-ListNode:找到环的入口节点无环返回 Noneifnotheadornothead.next:returnNone# 阶段1找相遇点slowfastheadwhilefastandfast.next:slowslow.nextfastfast.next.nextifslowfast:breakelse:returnNone# 无环# 阶段2找入口# 数学证明头到入口距离 相遇点到入口距离ptr1head ptr2slowwhileptr1!ptr2:ptr1ptr1.nextptr2ptr2.nextreturnptr1找中点deffind_middle(head:ListNode)-ListNode: 找到链表中间节点 偶数长度时返回第二个中间节点 slowfastheadwhilefastandfast.next:slowslow.next# 1步fastfast.next.next# 2步returnslow# fast 到尾时slow 在中点应用归并排序的链表版、重排链表、判断回文链表。3.4 技巧四删除倒数第 N 个节点双指针一次遍历defremove_nth_from_end(head:ListNode,n:int)-ListNode: 删除倒数第 n 个节点 时间O(n)空间O(1) dummyListNode(0,head)fastslowdummy# fast 先走 n1 步保持 slow 在目标前驱for_inrange(n1):fastfast.nextwhilefast:fastfast.nextslowslow.nextslow.nextslow.next.next# 删除returndummy.next原理fast与slow的距离恒为n1当fast到尾None时slow恰好在倒数第n1个节点目标的前驱。3.5 技巧五合并有序链表defmerge_two_lists(l1:ListNode,l2:ListNode)-ListNode: 合并两个升序链表 时间O(nm)空间O(1) dummyListNode(0)currdummywhilel1andl2:ifl1.vall2.val:curr.nextl1 l1l1.nextelse:curr.nextl2 l2l2.nextcurrcurr.nextcurr.nextl1ifl1elsel2# 连接剩余returndummy.next3.6 技巧六重排链表综合应用LeetCode 143将链表重新排列为L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...defreorder_list(head:ListNode)-None: 重排链表 1. 找中点快慢指针 2. 反转后半部分 3. 交替合并 ifnotheadornothead.next:return# 步骤1找中点slowfastheadwhilefastandfast.next:slowslow.nextfastfast.next.next# 步骤2反转后半部分prevNonecurrslow.nextslow.nextNone# 断开前后两部分whilecurr:next_tempcurr.nextcurr.nextprev prevcurr currnext_temp# 步骤3交替合并first,secondhead,prevwhilesecond:tmp1first.nexttmp2second.nextfirst.nextsecond second.nexttmp1 firsttmp1 secondtmp2四、双向链表与 LRU 缓存4.1 双向链表实现双向链表每个节点有前驱和后继指针支持 O(1) 的任意位置删除classDListNode:双向链表节点def__init__(self,key0,val0):self.keykey self.valval self.prevNoneself.nextNoneclassDoublyLinkedList:带头尾哨兵的双向链表def__init__(self):self.headDListNode()# 头哨兵self.tailDListNode()# 尾哨兵self.head.nextself.tail self.tail.prevself.head self.size0defadd_to_head(self,node:DListNode)-None:头部添加O(1)node.prevself.head node.nextself.head.nextself.head.next.prevnode self.head.nextnode self.size1defremove(self,node:DListNode)-None:删除指定节点O(1)已知节点地址node.prev.nextnode.nextnode.next.prevnode.prev self.size-1defmove_to_head(self,node:DListNode)-None:移到头部O(1)self.remove(node)self.add_to_head(node)defremove_tail(self)-DListNode:删除尾部O(1)nodeself.tail.prev self.remove(node)returnnode4.2 LRU 缓存LeetCode 146设计目标get和put操作均为 O(1)。数据结构组合哈希表key → nodeO(1) 查找双向链表维护访问顺序头部最近使用尾部最久未使用classLRUCache: LRU 缓存 get/put 时间复杂度O(1) def__init__(self,capacity:int):self.capacitycapacity self.cache{}# key → nodeself.dllDoublyLinkedList()defget(self,key:int)-int:ifkeynotinself.cache:return-1nodeself.cache[key]self.dll.move_to_head(node)# 更新为最近使用returnnode.valdefput(self,key:int,value:int)-None:ifkeyinself.cache:nodeself.cache[key]node.valvalue self.dll.move_to_head(node)else:ifself.dll.sizeself.capacity:tailself.dll.remove_tail()delself.cache[tail.key]# 淘汰最久未使用new_nodeDListNode(key,value)self.cache[key]new_node self.dll.add_to_head(new_node)# 验证cacheLRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))# 11变为最近使用cache.put(3,3)# 淘汰 key2print(cache.get(2))# -1已被淘汰cache.put(4,4)# 淘汰 key1print(cache.get(1))# -1print(cache.get(3))# 3print(cache.get(4))# 4五、链表 vs 其他数据结构操作单向链表双向链表带尾指针动态数组头部插入O(1)O(1)O(n)尾部插入O(n)O(1)O(1)均摊中间插入已知前驱O(1)O(1)O(n)头部删除O(1)O(1)O(n)尾部删除O(n)O(1)O(1)随机访问O(n)O(n)O(1)内存开销高指针更高双指针低连续六、链表问题决策树链表问题类型判断 ├── 需要修改头节点 → 使用虚拟头节点 ├── 需要找位置/中点/环 → 快慢指针 ├── 需要反转部分/全部 → 三指针迭代反转 ├── 需要删除倒数第N个 → 双指针间距n1 ├── 需要合并多个有序 → 虚拟头节点 多路归并 └── 需要O(1)的get/put且按访问排序 → 哈希表 双向链表七、核心心法链表问题的难点不在于逻辑而在于指针操作的精确性1. 画图辅助遇到复杂操作如反转、合并先在纸上画出指针变化再写代码。2. 边界检查清单头节点为空单节点链表操作后是否断链返回值是否正确dummy.next vs head3. 虚拟头节点的条件反射只要操作可能涉及头节点修改立即使用 dummy head省去 90% 的边界判断。4. 快慢指针的条件反射看到找中点、“判环”、倒数第 K等关键词立即考虑快慢指针。判断标准当你能在看到链表题目时10 秒内确定使用哪种技巧模式并能在纸上准确画出指针变化——链表才真正成为你的本能。