LeetCode链表算法精讲：高频题型与解题技巧-尧图网络科技

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, val=0, next=None): 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 slow

2.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 反转链表II（92题）

反转指定区间内的链表节点，需要特别注意边界处理：

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 环形链表II（142题）

在检测环的基础上找出环的起点：

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(a+b)=a+b+k环长 => a = k环长 - b

3.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_ptr<ListNode> 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, val=0, levels=1): self.val = val self.next = [None] * levels class SkipList: def __init__(self): self.head = SkipListNode(levels=32) 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] = node

6.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; } }