链表是面试中出现频率最高的数据结构之一。反转、合并、环检测、排序等经典操作考察对指针操作的精准掌控。
一、链表基础
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;
}