链表专题

链表是面试高频考点，重点掌握指针操作和虚拟头节点技巧

📊 题目总览

题目	难度	梯队	关键技巧
反转链表	⭐⭐	第一梯队	三指针迭代
K个一组翻转链表	⭐⭐⭐	第二梯队	分组反转
合并两个有序链表	⭐⭐	基础	虚拟头节点
合并K个排序链表	⭐⭐⭐	第三梯队	分治/堆
链表环检测	⭐⭐	第三梯队	快慢指针
链表中点	⭐⭐	基础	快慢指针

通用链表节点定义

javascript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// 辅助函数：从数组创建链表
function createLinkedList(arr) {
  if (!arr.length) return null;
  const head = new ListNode(arr[0]);
  let curr = head;
  for (let i = 1; i < arr.length; i++) {
    curr.next = new ListNode(arr[i]);
    curr = curr.next;
  }
  return head;
}

// 辅助函数：链表转数组
function linkedListToArray(head) {
  const result = [];
  while (head) {
    result.push(head.val);
    head = head.next;
  }
  return result;
}

1. 反转链表

LeetCode: 206. 反转链表 | 难度: 简单 | 梯队: 第一梯队 ✅

题目描述

给定单链表的头节点 head，反转链表并返回新的头节点。

输入: 1 -> 2 -> 3 -> 4 -> 5 -> null
输出: 5 -> 4 -> 3 -> 2 -> 1 -> null

核心思路

迭代法：使用三个指针 prev、curr、next，逐个反转指针方向
递归法：先递归到链表尾部，回溯时反转指针

代码实现

javascript

/**
 * 反转链表 - 迭代法（推荐）
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
  let prev = null;
  let curr = head;

  while (curr) {
    const next = curr.next;  // 1. 暂存下一个节点
    curr.next = prev;        // 2. 反转指针
    prev = curr;             // 3. prev 前进
    curr = next;             // 4. curr 前进
  }

  return prev;
}

/**
 * 反转链表 - 递归法
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseListRecursive(head) {
  // 递归终止：空节点或单节点
  if (!head || !head.next) return head;

  // 递归反转后续链表，返回新头节点
  const newHead = reverseListRecursive(head.next);

  // 反转当前节点：让下一个节点指向自己
  head.next.next = head;
  head.next = null;

  return newHead;
}

示例调用

javascript

// 基础示例
const list1 = createLinkedList([1, 2, 3, 4, 5]);
console.log(linkedListToArray(reverseList(list1)));
// 输出: [5, 4, 3, 2, 1]

// 边界条件：空链表
const list2 = createLinkedList([]);
console.log(linkedListToArray(reverseList(list2)));
// 输出: []

// 边界条件：单节点
const list3 = createLinkedList([1]);
console.log(linkedListToArray(reverseList(list3)));
// 输出: [1]

// 边界条件：两个节点
const list4 = createLinkedList([1, 2]);
console.log(linkedListToArray(reverseList(list4)));
// 输出: [2, 1]

复杂度分析

方法	时间复杂度	空间复杂度
迭代法	O(n)	O(1)
递归法	O(n)	O(n) 调用栈

2. K个一组翻转链表

LeetCode: 25. K 个一组翻转链表 | 难度: 困难 | 梯队: 第二梯队

可视化演示：点击查看算法动画

题目描述

给定链表头节点 head，每 k 个节点一组进行翻转。如果剩余节点不足 k 个，保持原顺序。

输入: head = [1,2,3,4,5], k = 2
输出: [2,1,4,3,5]

输入: head = [1,2,3,4,5], k = 3
输出: [3,2,1,4,5]

核心思路

使用虚拟头节点简化边界处理
每次先检查是否有 k 个节点
对每组执行反转，正确连接前后组

代码实现

javascript

/**
 * K 个一组翻转链表
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
function reverseKGroup(head, k) {
  // 虚拟头节点
  const dummy = new ListNode(0, head);
  let prevGroupEnd = dummy;

  while (head) {
    // 检查是否有 k 个节点
    let groupEnd = prevGroupEnd;
    for (let i = 0; i < k; i++) {
      groupEnd = groupEnd.next;
      if (!groupEnd) return dummy.next; // 不足 k 个，直接返回
    }

    const nextGroupStart = groupEnd.next;
    const groupStart = prevGroupEnd.next;

    // 反转当前组的 k 个节点
    let prev = nextGroupStart;
    let curr = groupStart;
    while (curr !== nextGroupStart) {
      const next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    // 连接反转后的组：prevGroupEnd -> groupEnd(新头) ... groupStart(新尾) -> nextGroupStart
    prevGroupEnd.next = groupEnd;
    prevGroupEnd = groupStart;
    head = nextGroupStart;
  }

  return dummy.next;
}

示例调用

javascript

// 基础示例：k=2
const list1 = createLinkedList([1, 2, 3, 4, 5]);
console.log(linkedListToArray(reverseKGroup(list1, 2)));
// 输出: [2, 1, 4, 3, 5]

// 基础示例：k=3
const list2 = createLinkedList([1, 2, 3, 4, 5]);
console.log(linkedListToArray(reverseKGroup(list2, 3)));
// 输出: [3, 2, 1, 4, 5]

// 边界条件：k=1（不变）
const list3 = createLinkedList([1, 2, 3]);
console.log(linkedListToArray(reverseKGroup(list3, 1)));
// 输出: [1, 2, 3]

// 边界条件：k 大于链表长度
const list4 = createLinkedList([1, 2]);
console.log(linkedListToArray(reverseKGroup(list4, 3)));
// 输出: [1, 2]

// 边界条件：空链表
console.log(linkedListToArray(reverseKGroup(null, 2)));
// 输出: []

// 边界条件：k 等于链表长度
const list5 = createLinkedList([1, 2, 3]);
console.log(linkedListToArray(reverseKGroup(list5, 3)));
// 输出: [3, 2, 1]

复杂度分析

时间: O(n)，每个节点被访问两次
空间: O(1)，只使用常量指针

3. 合并两个有序链表

LeetCode: 21. 合并两个有序链表 | 难度: 简单

题目描述

将两个升序链表合并为一个新的升序链表并返回。

代码实现

javascript

/**
 * 合并两个有序链表
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let curr = dummy;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      curr.next = l1;
      l1 = l1.next;
    } else {
      curr.next = l2;
      l2 = l2.next;
    }
    curr = curr.next;
  }

  // 连接剩余部分
  curr.next = l1 || l2;
  return dummy.next;
}

示例调用

javascript

// 基础示例
const l1 = createLinkedList([1, 2, 4]);
const l2 = createLinkedList([1, 3, 4]);
console.log(linkedListToArray(mergeTwoLists(l1, l2)));
// 输出: [1, 1, 2, 3, 4, 4]

// 边界条件：一个为空
console.log(linkedListToArray(mergeTwoLists(null, createLinkedList([1, 2]))));
// 输出: [1, 2]

// 边界条件：两个都为空
console.log(linkedListToArray(mergeTwoLists(null, null)));
// 输出: []

// 边界条件：长度不等
const l3 = createLinkedList([1]);
const l4 = createLinkedList([2, 3, 4, 5]);
console.log(linkedListToArray(mergeTwoLists(l3, l4)));
// 输出: [1, 2, 3, 4, 5]

复杂度分析

时间: O(n + m)
空间: O(1)

4. 合并K个排序链表

LeetCode: 23. 合并K个升序链表 | 难度: 困难 | 梯队: 第三梯队

可视化演示：点击查看算法动画

题目描述

给定 k 个升序链表数组，将所有链表合并到一个升序链表中。

核心思路

分治法（推荐）：两两合并，时间 O(N log k)
最小堆：将所有头节点入堆，每次取最小

代码实现

javascript

/**
 * 合并K个排序链表 - 分治法
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
function mergeKLists(lists) {
  if (!lists.length) return null;
  if (lists.length === 1) return lists[0];

  const mid = Math.floor(lists.length / 2);
  const left = mergeKLists(lists.slice(0, mid));
  const right = mergeKLists(lists.slice(mid));

  return mergeTwoLists(left, right);
}

示例调用

javascript

// 基础示例
const lists1 = [
  createLinkedList([1, 4, 5]),
  createLinkedList([1, 3, 4]),
  createLinkedList([2, 6])
];
console.log(linkedListToArray(mergeKLists(lists1)));
// 输出: [1, 1, 2, 3, 4, 4, 5, 6]

// 边界条件：空数组
console.log(linkedListToArray(mergeKLists([])));
// 输出: []

// 边界条件：包含空链表
const lists2 = [null, createLinkedList([1, 2]), null];
console.log(linkedListToArray(mergeKLists(lists2)));
// 输出: [1, 2]

// 边界条件：单个链表
const lists3 = [createLinkedList([1, 2, 3])];
console.log(linkedListToArray(mergeKLists(lists3)));
// 输出: [1, 2, 3]

复杂度分析

时间: O(N log k)，N 为总节点数，k 为链表数
空间: O(log k) 递归栈

5. 链表环检测

LeetCode: 141. 环形链表 / 142. 环形链表 II | 难度: 中等 | 梯队: 第三梯队

题目描述

判断链表是否有环
找到环的入口节点

核心思路

Floyd 快慢指针算法：

慢指针每次走 1 步，快指针每次走 2 步
若有环，快慢必在环内相遇
从 head 和相遇点同速前进，再次相遇即入口

代码实现

javascript

/**
 * 判断链表是否有环
 * @param {ListNode} head
 * @return {boolean}
 */
function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
}

/**
 * 找到环的入口节点
 * @param {ListNode} head
 * @return {ListNode}
 */
function detectCycle(head) {
  let slow = head;
  let fast = head;

  // 找到相遇点
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      // 从 head 和相遇点同时出发
      let ptr = head;
      while (ptr !== slow) {
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr;
    }
  }

  return null;
}

示例调用

javascript

// 创建带环链表: 1 -> 2 -> 3 -> 4 -> 2 (环)
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // 形成环

console.log(hasCycle(node1));       // true
console.log(detectCycle(node1).val); // 2 (入口节点值)

// 无环链表
const list1 = createLinkedList([1, 2, 3]);
console.log(hasCycle(list1));        // false
console.log(detectCycle(list1));     // null

// 边界条件：空链表
console.log(hasCycle(null));         // false

// 边界条件：单节点无环
console.log(hasCycle(new ListNode(1))); // false

// 边界条件：单节点自环
const selfLoop = new ListNode(1);
selfLoop.next = selfLoop;
console.log(hasCycle(selfLoop));     // true
console.log(detectCycle(selfLoop).val); // 1

数学证明

设 head 到环入口距离为 a，环入口到相遇点距离为 b，相遇点到环入口距离为 c：

相遇时：slow = a + b，fast = a + b + n(b + c)
由于 fast = 2 * slow：a = c + (n-1)(b + c)
所以从 head 和相遇点同速前进，必在入口相遇

复杂度分析

时间: O(n)
空间: O(1)

6. 链表中点

LeetCode: 876. 链表的中间结点 | 难度: 简单

题目描述

给定链表头节点，返回中间节点。如果有两个中间节点，返回第二个。

代码实现

javascript

/**
 * 找到链表中点
 * @param {ListNode} head
 * @return {ListNode}
 */
function middleNode(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

示例调用

javascript

// 奇数个节点：返回正中间
const list1 = createLinkedList([1, 2, 3, 4, 5]);
console.log(middleNode(list1).val); // 3

// 偶数个节点：返回第二个中间节点
const list2 = createLinkedList([1, 2, 3, 4]);
console.log(middleNode(list2).val); // 3

// 边界条件：单节点
const list3 = createLinkedList([1]);
console.log(middleNode(list3).val); // 1

// 边界条件：两个节点
const list4 = createLinkedList([1, 2]);
console.log(middleNode(list4).val); // 2

复杂度分析

时间: O(n)
空间: O(1)

💡 链表题目技巧总结

技巧	适用场景	示例题目
虚拟头节点	头节点可能变化	反转链表、合并链表
快慢指针	找中点、判环	环检测、链表中点
三指针	原地反转	反转链表
分治法	多链表合并	合并K个链表

javascript

// 万能开头：虚拟头节点
const dummy = new ListNode(0, head);
// 最后返回 dummy.next

链表专题 ​

📊 题目总览 ​

通用链表节点定义 ​

1. 反转链表 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

2. K个一组翻转链表 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

3. 合并两个有序链表 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

4. 合并K个排序链表 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

5. 链表环检测 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

数学证明 ​

复杂度分析 ​

6. 链表中点 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

💡 链表题目技巧总结 ​

链表专题

📊 题目总览

通用链表节点定义

1. 反转链表

题目描述

核心思路

代码实现

示例调用

复杂度分析

2. K个一组翻转链表

题目描述

核心思路

代码实现

示例调用

复杂度分析

3. 合并两个有序链表

题目描述

代码实现

示例调用

复杂度分析

4. 合并K个排序链表

题目描述

核心思路

代码实现

示例调用

复杂度分析

5. 链表环检测

题目描述

核心思路

代码实现

示例调用

数学证明

复杂度分析

6. 链表中点

题目描述

代码实现

示例调用

复杂度分析

💡 链表题目技巧总结