1. LeetCode Hot 100 链表专题精讲链表作为数据结构中的基础类型在算法面试中出现的频率极高。根据历年LeetCode高频题库统计链表类题目约占Hot 100题库的15%其中既包含基础的指针操作也涉及复杂的算法思想。本文将系统梳理链表类题目的解题框架结合C/C和Python两种语言特性通过7道经典题目展示链表操作的通用解法。注本文代码示例会同时展示C和Python实现因链表操作涉及指针/引用细节不同语言的实现方式差异较大1.1 链表数据结构核心要点链表与数组最大的区别在于存储方式——非连续内存通过指针链接。这种特性带来两个关键特征插入/删除时间复杂度O(1)已知节点位置时随机访问时间复杂度O(n)// C 链表节点典型定义 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };# Python 链表节点定义 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next链表问题的解题核心通常围绕以下几个操作展开指针的移动与追踪快慢指针节点关系的修改反转、交换虚拟头节点的运用处理边界情况递归与迭代的转换1.2 Hot 100链表题高频考点分布根据题目出现频率排序反转链表206题合并两个有序链表21题环形链表检测141题删除倒数第N个节点19题两数相加2题相交链表160题复杂链表复制138题2. 链表基础操作框架2.1 虚拟头节点技巧当需要处理链表头节点可能被修改的情况时引入dummy节点可以简化操作ListNode* dummy new ListNode(-1); dummy-next head; // ...操作过程... return dummy-next;dummy ListNode(-1, head) curr dummy # ...操作过程... return dummy.next注意事项C版本需要手动释放dummy节点内存否则会造成内存泄漏2.2 快慢指针经典应用快指针速度是慢指针的两倍可用于找链表中点876题检测环形链表141题找倒数第N个节点19题def find_middle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next return slow2.3 链表反转的三种实现迭代法推荐ListNode* reverseList(ListNode* head) { ListNode *prev nullptr; while (head) { ListNode *next head-next; head-next prev; prev head; head next; } return prev; }递归法def reverseList(head): if not head or not head.next: return head new_head reverseList(head.next) head.next.next head head.next None return new_head头插法ListNode* reverseByInsert(ListNode* head) { ListNode dummy(0); while (head) { ListNode *next head-next; head-next dummy.next; dummy.next head; head next; } return dummy.next; }3. 高频题目深度解析3.1 反转链表II92题反转指定区间内的链表节点需要特别注意边界处理def reverseBetween(head, m, n): dummy ListNode(0, head) pre dummy for _ in range(m - 1): pre pre.next curr pre.next for _ in range(n - m): temp curr.next curr.next temp.next temp.next pre.next pre.next temp return dummy.next关键点先定位到m-1位置的pre节点将后续节点逐个移动到pre后面共需要n-m次操作3.2 环形链表II142题在检测环的基础上找出环的起点ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; } } return nullptr; }数学原理设头节点到环起点距离a环起点到相遇点距离b快指针路程 a b k*环长慢指针路程 a b由2(ab)abk环长 a k环长 - b3.3 合并K个升序链表23题使用优先队列的解法import heapq def mergeKLists(lists): dummy curr ListNode(0) heap [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) while heap: val, i, node heapq.heappop(heap) curr.next node curr curr.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next时间复杂度分析建堆O(k)每次取最小O(logk)共n个节点 O(nlogk)4. 链表问题调试技巧4.1 可视化打印链表调试时打印链表结构可快速定位问题void printList(ListNode* head) { while (head) { cout head-val; if (head-next) cout -; head head-next; } cout -NULL endl; }4.2 常见错误排查指针丢失修改next指针前必须先保存// 错误写法 head-next new_node; // 原head-next丢失 new_node-next head-next; // 正确写法 ListNode* temp head-next; head-next new_node; new_node-next temp;循环引用反转链表时可能意外形成环边界条件头节点/尾节点需要特殊处理4.3 内存管理要点C使用new创建节点后必须delete异常处理时确保释放已分配内存推荐使用智能指针管理链表struct ListNode { int val; shared_ptrListNode next; ListNode(int x) : val(x), next(nullptr) {} };5. 进阶题目挑战5.1 LRU缓存实现146题双向链表哈希表的经典应用class LRUCache: def __init__(self, capacity): self.cap capacity self.cache {} self.head ListNode(0, 0) self.tail ListNode(0, 0) self.head.next self.tail self.tail.prev self.head def _remove(self, node): p, n node.prev, node.next p.next, n.prev n, p def _add(self, node): p self.tail.prev p.next node node.prev p node.next self.tail 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(key, value) self._add(node) self.cache[key] node if len(self.cache) self.cap: node self.head.next self._remove(node) del self.cache[node.key]5.2 复制带随机指针的链表138题O(1)空间复杂度的解法Node* copyRandomList(Node* head) { if (!head) return nullptr; // 第一步复制节点 Node* curr head; while (curr) { Node* copy new Node(curr-val); copy-next curr-next; curr-next copy; curr copy-next; } // 第二步处理random指针 curr head; while (curr) { if (curr-random) { curr-next-random curr-random-next; } curr curr-next-next; } // 第三步分离链表 Node* newHead head-next; curr head; while (curr) { Node* temp curr-next; curr-next temp-next; if (temp-next) { temp-next temp-next-next; } curr curr-next; } return newHead; }6. 链表与其他数据结构的结合6.1 跳表设计1206题链表多级索引的平衡结构import random class SkipListNode: def __init__(self, val0, levels1): self.val val self.next [None] * levels class SkipList: def __init__(self): self.head SkipListNode(levels32) self.levels 1 def _random_level(self): level 1 while random.random() 0.25 and level 32: level 1 return level def search(self, target): curr self.head for i in reversed(range(self.levels)): while curr.next[i] and curr.next[i].val target: curr curr.next[i] if curr.next[i] and curr.next[i].val target: return True return False def add(self, num): update [None] * 32 curr self.head for i in reversed(range(self.levels)): while curr.next[i] and curr.next[i].val num: curr curr.next[i] update[i] curr level self._random_level() if level self.levels: for i in range(self.levels, level): update[i] self.head self.levels level node SkipListNode(num, level) for i in range(level): node.next[i] update[i].next[i] update[i].next[i] node6.2 二叉树转为链表114题前序遍历的变形void flatten(TreeNode* root) { TreeNode* curr root; while (curr) { if (curr-left) { TreeNode* pred curr-left; while (pred-right) { pred pred-right; } pred-right curr-right; curr-right curr-left; curr-left nullptr; } curr curr-right; } }7. 链表专题训练建议建议刷题顺序单链表基础206→141→21→19进阶操作92→142→138综合应用146→23→148时间分配建议基础题目每道30分钟内完成中等难度题目控制在45分钟困难题目不超过60分钟常见面试考察点指针操作熟练度现场手写代码边界条件处理能力时间/空间复杂度分析多解法比较递归vs迭代推荐练习方法先自己尝试实现再对比优秀解法记录每种题型的解题模板定期复习易错题目参加周赛检验学习效果对于链表问题我个人的经验是一定要在纸上画出节点指针的变化过程很多问题在可视化后就会变得清晰。另外建议至少掌握递归和迭代两种实现方式不同场景下各有优势。