链表是面试中出现频率最高的数据结构之一。反转、合并、环检测、排序等经典操作考察对指针操作的精准掌控。
一、链表基础
Mermaid · 渲染中（下方为源码）
graph LR A[链表操作] --> B[反转] A --> C[合并] A --> D[环检测] A --> E[排序]
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}虚拟头节点（Dummy Node）
// 避免对头节点的特殊处理
ListNode dummy = new ListNode(0);
dummy.next = head;
// 操作完成后返回 dummy.next二、反转链表（LeetCode 206）
迭代
ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}递归
ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}三、环检测（LeetCode 141/142）
快慢指针判环
boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}找环入口
ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}四、合并两个有序链表（LeetCode 21）
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
else { cur.next = l2; l2 = l2.next; }
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}五、删除倒数第 N 个节点（LeetCode 19）
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) fast = fast.next;
while (fast != null) { fast = fast.next; slow = slow.next; }
slow.next = slow.next.next;
return dummy.next;
}六、链表排序（LeetCode 148）
归并排序：快慢指针找中点 → 递归拆分 → 合并。
ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode mid = getMid(head);
ListNode right = mid.next;
mid.next = null;
return mergeTwoLists(sortList(head), sortList(right));
}
ListNode getMid(ListNode head) {
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}七、其他高频题
| 题目 | 技巧 |
|---|---|
| 回文链表（234） | 找中点 + 反转后半 + 比较 |
| 相交链表（160） | 双指针等长技巧 |
| K 个一组反转（25） | 分组反转 + 连接 |
| 复制带随机指针（138） | 交织法 / HashMap |
| LRU 缓存（146） | 双向链表 + HashMap |
八、面试要点
- Dummy 节点：统一处理头节点
- 快慢指针：找中点、判环、找倒数第 k 个
- 反转三指针：prev, cur, next
- 递归思维：链表天然递归结构
- LeetCode：206、21、141/142、19、25、148、234、160