1. 链表专题概述链表是计算机科学中最基础的数据结构之一也是算法面试中的高频考点。在LeetCode Hot100这类经典算法题库中链表相关题目占据了相当比例。链表结构简单却变化多端从基础的单链表操作到复杂的环形链表检测都需要程序员对指针操作有深刻理解。链表与数组最大的区别在于内存布局。数组需要连续的内存空间而链表的节点可以分散在内存各处通过指针连接。这种特性使链表在插入删除操作上具有O(1)时间复杂度优势但牺牲了随机访问能力。实际工程中链表常用于实现哈希表冲突处理、操作系统进程调度、浏览器历史记录等场景。2. 链表核心操作解析2.1 基本结构定义以C为例典型的单链表节点定义如下struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };关键点在于val存储节点值next指针指向下一个节点构造函数初始化节点值并将next置空在Java中更常用类实现class ListNode { int val; ListNode next; ListNode(int x) { val x; } }2.2 链表基本操作2.2.1 遍历链表def traverse(head): current head while current is not None: print(current.val) current current.next注意事项循环条件检查current而非current.next尾节点的next应指向None/nullptr时间复杂度O(n)空间复杂度O(1)2.2.2 插入节点在pre节点后插入新节点def insert(pre, val): new_node ListNode(val) new_node.next pre.next pre.next new_node关键步骤创建新节点新节点next指向pre原nextpre的next指向新节点2.2.3 删除节点删除pre后的节点def delete(pre): if pre.next: pre.next pre.next.next注意检查pre.next是否存在避免空指针异常。3. Hot100经典链表题型3.1 反转链表LeetCode 206迭代解法def reverseList(head): prev None curr head while curr: next_temp curr.next curr.next prev prev curr curr next_temp return prev递归解法def reverseList(head): if not head or not head.next: return head p reverseList(head.next) head.next.next head head.next None return p关键点迭代法需要维护prev/curr/next三指针递归法要注意终止条件和指针修改顺序两种方法时间复杂度都是O(n)3.2 环形链表检测LeetCode 141快慢指针解法def hasCycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False技巧快指针每次走两步慢指针每次走一步相遇说明有环快指针走到末尾说明无环时间复杂度O(n)空间复杂度O(1)3.3 合并两个有序链表LeetCode 21迭代解法def mergeTwoLists(l1, l2): dummy ListNode(0) curr dummy while l1 and l2: if l1.val l2.val: curr.next l1 l1 l1.next else: curr.next l2 l2 l2.next curr curr.next curr.next l1 if l1 else l2 return dummy.next递归解法def mergeTwoLists(l1, l2): if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next mergeTwoLists(l1.next, l2) return l1 else: l2.next mergeTwoLists(l1, l2.next) return l2注意使用dummy节点简化边界处理剩余链表直接拼接无需逐个节点处理时间复杂度O(mn)4. 链表解题技巧4.1 虚拟头节点技巧在链表问题中头节点的特殊处理常常导致代码复杂。引入dummy节点可以统一处理逻辑dummy ListNode(0) dummy.next head # ...处理逻辑... return dummy.next适用场景可能需要修改头节点的问题需要维护前驱节点的问题需要返回新链表的场景4.2 快慢指针应用快慢指针不仅能检测环还能解决找链表中点slow fast head while fast and fast.next: slow slow.next fast fast.next.next # slow即为中点找倒数第k个节点fast slow head for _ in range(k): fast fast.next while fast: slow slow.next fast fast.next4.3 链表排序算法链表最适合的排序算法是归并排序def sortList(head): if not head or not head.next: return head # 找中点 slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next # 分割链表 mid slow.next slow.next None # 递归排序 left sortList(head) right sortList(mid) # 合并 return merge(left, right)特点时间复杂度O(nlogn)空间复杂度O(logn)来自递归栈稳定排序5. 链表问题调试技巧5.1 可视化链表打印链表辅助调试def printList(head): res [] while head: res.append(str(head.val)) head head.next print(-.join(res))对于环形链表可限制打印节点数量def printCycleList(head, max_len20): res [] count 0 while head and count max_len: res.append(str(head.val)) head head.next count 1 print(-.join(res))5.2 常见错误排查指针丢失# 错误写法 curr.next prev curr curr.next # curr已经变成prev # 正确写法 next_temp curr.next curr.next prev curr next_temp边界条件空链表处理单节点链表头尾节点特殊处理环形引用修改指针时意外创建环需要断开原有链接时忘记处理6. 工程中的链表应用6.1 LRU缓存实现链表哈希表的经典应用class LRUCache: def __init__(self, capacity): self.capacity capacity self.cache {} self.head ListNode(0) self.tail ListNode(0) self.head.next self.tail self.tail.prev self.head def _remove(self, node): prev, next node.prev, node.next prev.next, next.prev next, prev def _add(self, node): node.prev self.tail.prev node.next self.tail self.tail.prev.next node self.tail.prev node def get(self, key): if key in self.cache: node self.cache[key] self._remove(node) self._add(node) return node.val return -1 def put(self, key, value): if key in self.cache: self._remove(self.cache[key]) node ListNode(value) self._add(node) self.cache[key] node if len(self.cache) self.capacity: lru self.head.next self._remove(lru) del self.cache[lru.key]6.2 多级链表展开类似扁平化多级双向链表问题LeetCode 430def flatten(head): if not head: return head dummy ListNode(0) curr dummy stack [head] while stack: node stack.pop() if node.next: stack.append(node.next) if node.child: stack.append(node.child) node.child None curr.next node node.prev curr curr node dummy.next.prev None return dummy.next7. 进阶链表问题7.1 复杂链表复制LeetCode 138带随机指针的链表复制def copyRandomList(head): if not head: return None # 创建交织链表 curr head while curr: new_node Node(curr.val) new_node.next curr.next curr.next new_node curr new_node.next # 复制random指针 curr head while curr: if curr.random: curr.next.random curr.random.next curr curr.next.next # 分离链表 old head new head.next new_head head.next while old: old.next old.next.next new.next new.next.next if new.next else None old old.next new new.next return new_head7.2 链表排序LeetCode 148自底向上的归并排序O(1)空间def sortList(head): def merge(l1, l2): dummy ListNode(0) curr dummy while l1 and l2: if l1.val l2.val: curr.next l1 l1 l1.next else: curr.next l2 l2 l2.next curr curr.next curr.next l1 if l1 else l2 return dummy.next if not head or not head.next: return head length 0 node head while node: length 1 node node.next dummy ListNode(0) dummy.next head step 1 while step length: prev, curr dummy, dummy.next while curr: left curr right split(left, step) curr split(right, step) prev.next merge(left, right) while prev.next: prev prev.next step 1 return dummy.next def split(head, step): if not head: return None for _ in range(step - 1): if head.next: head head.next else: break next_head head.next head.next None return next_head8. 链表专题总结链表问题的核心在于指针操作需要特别注意指针修改顺序避免丢失引用边界条件处理空链表、单节点、头尾节点循环终止条件判断多指针协同快慢指针、前后指针在Hot100这类题库中链表题目往往考察基础操作能力反转、合并、删除双指针技巧应用复杂问题的分解能力边界条件的周全考虑实际面试中建议先厘清题意明确输入输出画图分析指针变化考虑边界情况写完代码后人工验证几个测试用例