链表必刷 8 题
链表题目考察指针操作的细心程度。掌握以下 8 题，面试链表问题基本全覆盖。
1. 反转链表（LeetCode 206）
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
递归版本：
def reverse_list_recursive(head):
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head
head.next = None
return new_head
2. 合并两个有序链表（LeetCode 21）
def merge_two_lists(l1, l2):
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next, l1 = l1, l1.next
else:
tail.next, l2 = l2, l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
3. 环形链表（LeetCode 141/142）
检测环：快慢指针
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
找环入口：
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
数学证明：设环前长度为 a，环长度为 b，相遇时慢指针走 a + x，快指针走 a + x + kb。因为快是慢的 2 倍：2(a + x) = a + x + kb → a + x = kb → a = kb - x。从 head 和相遇点同时走，在环入口相遇。
4. 相交链表（LeetCode 160）
def get_intersection_node(headA, headB):
a, b = headA, headB
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
原理：两个指针各走 len(A) + len(B) 步，在交点或 null 相遇。
5. 奇偶链表（LeetCode 328）
def odd_even_list(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
6. 删除倒数第 N 个节点（LeetCode 19）
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
7. 排序链表（LeetCode 148）
归并排序，O(n log n) 时间，O(1) 空间（迭代版本）：
def sort_list(head):
if not head or not head.next:
return head
def split(head, step):
for _ in range(step - 1):
if head:
head = head.next
if not head:
return None
next_head = head.next
head.next = None
return next_head
def merge(l1, l2, tail):
while l1 and l2:
if l1.val < l2.val:
tail.next, l1 = l1, l1.next
else:
tail.next, l2 = l2, l2.next
tail = tail.next
tail.next = l1 or l2
while tail.next:
tail = tail.next
return tail
dummy = ListNode(0)
dummy.next = head
length = 0
while head:
length += 1
head = head.next
step = 1
while step < length:
curr = dummy.next
tail = dummy
while curr:
l1 = curr
l2 = split(l1, step)
curr = split(l2, step) if l2 else None
tail = merge(l1, l2, tail)
step *= 2
return dummy.next
8. LRU 缓存（LeetCode 146）
见 哈希表文章 或参考以下精简版：
class Node:
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_head(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
elif len(self.cache) >= self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
node = Node(key, value)
self.cache[key] = node
self._add_to_head(node)
链表技巧总结
| 技巧 | 应用 |
|---|---|
| 哑节点 | 简化边界（删除头节点等） |
| 快慢指针 | 环检测、中点查找、倒数第 N |
| 迭代反转 | 反转链表、K 个一组反转 |
| 归并排序 | 链表排序（O(1) 空间） |
| 哈希 + 双向链表 | LRU、LFU |
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。