13.2 链表操作
面试重要程度：⭐⭐⭐⭐⭐
常见提问方式： "手写反转链表" "检测链表环" "合并有序链表"
预计阅读时间：35分钟
🔗 链表基础结构
链表节点定义
/**
* 链表节点定义
*/
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
/**
* 双向链表节点
*/
public class DoublyListNode {
int val;
DoublyListNode prev;
DoublyListNode next;
DoublyListNode() {}
DoublyListNode(int val) { this.val = val; }
}
🔄 反转链表系列
基础反转操作
/**
* 链表反转经典问题
*/
public class LinkedListReverse {
/**
* 反转链表
* LeetCode 206: Reverse Linked List
*/
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
/**
* 递归方式反转链表
*/
public ListNode reverseListRecursive(ListNode head) {
// 递归终止条件
if (head == null || head.next == null) {
return head;
}
// 递归反转后面的链表
ListNode newHead = reverseListRecursive(head.next);
// 反转当前连接
head.next.next = head;
head.next = null;
return newHead;
}
/**
* 反转链表II - 反转指定区间
* LeetCode 92: Reverse Linked List II
*/
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null || left == right) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
// 找到反转区间的前一个节点
for (int i = 0; i < left - 1; i++) {
prev = prev.next;
}
// 反转区间内的节点
ListNode current = prev.next;
for (int i = 0; i < right - left; i++) {
ListNode nextNode = current.next;
current.next = nextNode.next;
nextNode.next = prev.next;
prev.next = nextNode;
}
return dummy.next;
}
/**
* K个一组翻转链表
* LeetCode 25: Reverse Nodes in k-Group
*/
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) return head;
// 检查剩余节点是否足够k个
ListNode current = head;
int count = 0;
while (current != null && count < k) {
current = current.next;
count++;
}
if (count == k) {
// 递归处理后续节点
current = reverseKGroup(current, k);
// 反转当前k个节点
while (count > 0) {
ListNode nextTemp = head.next;
head.next = current;
current = head;
head = nextTemp;
count--;
}
head = current;
}
return head;
}
}
🔍 链表环检测
环检测算法
/**
* 链表环检测相关问题
*/
public class LinkedListCycle {
/**
* 环形链表检测
* LeetCode 141: Linked List Cycle
*/
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
/**
* 环形链表II - 返回环的起始节点
* LeetCode 142: Linked List Cycle II
*/
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
// 第一次相遇：检测是否有环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
if (fast == null || fast.next == null) return null;
// 第二次相遇：找到环的起始节点
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
/**
* 环形链表的长度
*/
public int cycleLength(ListNode head) {
if (head == null || head.next == null) return 0;
ListNode slow = head;
ListNode fast = head;
// 检测环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
if (fast == null || fast.next == null) return 0;
// 计算环的长度
int length = 1;
fast = fast.next;
while (slow != fast) {
fast = fast.next;
length++;
}
return length;
}
/**
* 快乐数（使用链表环检测思想）
* LeetCode 202: Happy Number
*/
public boolean isHappy(int n) {
int slow = n;
int fast = getNext(n);
while (fast != 1 && slow != fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast == 1;
}
private int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
}
🔗 合并有序链表
合并操作
/**
* 链表合并相关问题
*/
public class LinkedListMerge {
/**
* 合并两个有序链表
* LeetCode 21: Merge Two Sorted Lists
*/
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
// 连接剩余节点
current.next = list1 != null ? list1 : list2;
return dummy.next;
}
/**
* 递归方式合并两个有序链表
*/
public ListNode mergeTwoListsRecursive(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val <= list2.val) {
list1.next = mergeTwoListsRecursive(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoListsRecursive(list1, list2.next);
return list2;
}
}
/**
* 合并K个升序链表
* LeetCode 23: Merge k Sorted Lists
*/
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return mergeKListsHelper(lists, 0, lists.length - 1);
}
private ListNode mergeKListsHelper(ListNode[] lists, int start, int end) {
if (start == end) return lists[start];
if (start > end) return null;
int mid = start + (end - start) / 2;
ListNode left = mergeKListsHelper(lists, start, mid);
ListNode right = mergeKListsHelper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
/**
* 使用优先队列合并K个链表
*/
public ListNode mergeKListsWithPQ(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// 将所有链表的头节点加入优先队列
for (ListNode list : lists) {
if (list != null) {
pq.offer(list);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
current.next = node;
current = current.next;
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}
}
🎯 链表高级操作
复杂链表操作
/**
* 链表高级操作
*/
public class AdvancedLinkedListOperations {
/**
* 删除链表的倒数第N个节点
* LeetCode 19: Remove Nth Node From End of List
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// 让first先走n+1步
for (int i = 0; i <= n; i++) {
first = first.next;
}
// 同时移动first和second
while (first != null) {
first = first.next;
second = second.next;
}
// 删除倒数第n个节点
second.next = second.next.next;
return dummy.next;
}
/**
* 链表的中间节点
* LeetCode 876: Middle of the Linked List
*/
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
/**
* 回文链表
* LeetCode 234: Palindrome Linked List
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// 找到中点
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 反转后半部分
ListNode secondHalf = reverseList(slow.next);
// 比较前半部分和后半部分
ListNode firstHalf = head;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
/**
* 相交链表
* LeetCode 160: Intersection of Two Linked Lists
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA;
ListNode pB = headB;
// 当pA和pB相遇时，要么在交点，要么都为null
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
/**
* 复制带随机指针的链表
* LeetCode 138: Copy List with Random Pointer
*/
static class RandomListNode {
int val;
RandomListNode next;
RandomListNode random;
public RandomListNode(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
Map<RandomListNode, RandomListNode> map = new HashMap<>();
// 第一遍：创建所有节点
RandomListNode current = head;
while (current != null) {
map.put(current, new RandomListNode(current.val));
current = current.next;
}
// 第二遍：设置next和random指针
current = head;
while (current != null) {
map.get(current).next = map.get(current.next);
map.get(current).random = map.get(current.random);
current = current.next;
}
return map.get(head);
}
/**
* 空间优化版本：原地复制
*/
public RandomListNode copyRandomListOptimized(RandomListNode head) {
if (head == null) return null;
// 第一步：在每个节点后插入复制节点
RandomListNode current = head;
while (current != null) {
RandomListNode copy = new RandomListNode(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
// 第二步：设置复制节点的random指针
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// 第三步：分离原链表和复制链表
RandomListNode dummy = new RandomListNode(0);
RandomListNode copyPrev = dummy;
current = head;
while (current != null) {
RandomListNode copy = current.next;
current.next = copy.next;
copyPrev.next = copy;
copyPrev = copy;
current = current.next;
}
return dummy.next;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
💡 面试常见问题解答
Q1: 链表反转的多种实现方式？
标准回答：
链表反转实现方式： 1. 迭代方式 - 使用三个指针：prev、current、next - 时间复杂度O(n)，空间复杂度O(1) - 最常用，效率最高 2. 递归方式 - 递归到链表末尾，然后逐层返回 - 时间复杂度O(n)，空间复杂度O(n) - 代码简洁，但有栈溢出风险 3. 栈辅助 - 将节点压入栈，再依次弹出重建 - 时间复杂度O(n)，空间复杂度O(n) - 思路直观，但额外空间开销大 推荐使用迭代方式，效率高且稳定。
Q2: 如何检测链表中的环？
标准回答：
链表环检测方法： 1. Floyd判圈算法（快慢指针） - 快指针每次走2步，慢指针每次走1步 - 如果有环，快慢指针必定相遇 - 时间复杂度O(n)，空间复杂度O(1) 2. 哈希表方法 - 遍历链表，记录访问过的节点 - 如果重复访问某节点，说明有环 - 时间复杂度O(n)，空间复杂度O(n) 3. 环起始点定位 - 快慢指针相遇后，重置一个指针到头部 - 两指针同速前进，再次相遇点即为环起始点 推荐使用Floyd算法，空间效率最优。
Q3: 合并多个有序链表的最优策略？
标准回答：
合并K个有序链表策略： 1. 逐一合并 - 依次合并每两个链表 - 时间复杂度O(k²n)，效率较低 2. 分治合并 - 类似归并排序，两两配对合并 - 时间复杂度O(nk log k)，推荐方案 3. 优先队列 - 维护k个链表的头节点最小堆 - 时间复杂度O(nk log k)，空间复杂度O(k) 4. 实现要点 - 注意空链表的处理 - 使用虚拟头节点简化代码 - 递归深度控制 分治合并是最优解，兼顾时间和空间效率。
核心要点总结：
- ✅ 掌握链表反转的迭代和递归实现
- ✅ 熟练使用快慢指针检测环和找中点
- ✅ 理解链表合并的分治策略
- ✅ 能够处理复杂链表结构的深拷贝问题
Java面试圣经 文章被收录于专栏
Java面试圣经
投递美团等公司10个岗位
阿里巴巴公司福利 662人发布
查看4道真题和解析