「重学算法」快速掌握链表题

前言

算法是程序员必须修炼的一门内功（例如：张无忌修炼九阳神功），更是阿里、腾讯、字节这些大厂面试考察的重中之重。为了攻克算法面试拿下心仪 Offer，很多程序员面试前都会在 LeetCode 上疯狂刷题备战面试。

然而面对刷不完的题目，我们很难在短时间内全部熟练掌握，那该如何高效准备，快速掌握刷题、解题技巧，从容应对即将到来的算法面试？

我们可以从以下几个方面出发：

• 数组、字符串、链表、队列、树、栈、队列、图、前缀树、分段树和树状数组等数据结构，逐个击破。
• 总结常用算法，归并、快排、拓扑，如何二分查找、递归、回溯，以及广度与深度优先、动态规划等。
• 刻意练习，针对具有代表性的真题深入剖析，完善自己的算法知识体系。

温馨提示：本文主要说一说链表类题目的解决思路和代码。适合算法初学者、社招准备面试和对算法感兴趣的同学们。

206. 反转链表

题目

来源：力扣（LeetCode）206 反转链表 (opens new window)

难度：简单

反转一个单链表。

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路

假设存在链表 1 → 2 → 3 → ∅ ，我们想要把它改成 ∅ ← 1 ← 2 ← 3 。

• 在遍历列表时，将当前节点的 next 指针改为指向前一个元素。
• 由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。
• 在更改引用之前，还需要另一个指针来存储下一个节点。
• 不要忘记在最后返回新的头引用！

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */

let reverseList = (head) => {
  if (!head) {
    return null;
  }
  let pre = null;
  let cur = head;
  while (cur) {
    let nextCache = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nextCache;
  }
  return pre;
};

复杂度

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
• 空间复杂度：O(1)。

92. 反转链表 II

题目

来源：力扣（LeetCode）92 反转链表 II (opens new window)

难度：中等

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:


输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路

假设我们需要反转下图中的蓝色区域。

使用「206. 反转链表」的解法，反转 left 到 right 部分以后，再拼接起来。我们还需要记录 left 的前一个节点，和 right 的后一个节点。如图所示：

算法逻辑：

• 先将待反转的区域反转。
• 把 pre 的 next 指针指向反转后的链表头节点，反转后的链表尾节点的 next 指针指向 succ 。

温馨提示：可以自己画图理清思路，后面编码会更顺畅。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var reverseBetween = function(head, left, right) {
  // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
  const dummyNode = new ListNode(-1);
  dummyNode.next = head;

  let pre = dummyNode;
  // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
  // 建议写在 for 循环里，语义清晰
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next;
  }

  // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
  let rightNode = pre;
  for (let i = 0; i < right - left + 1; i++) {
    rightNode = rightNode.next;
  }

  // 第 3 步：切断出一个子链表（截取链表）
  let leftNode = pre.next;
  let curr = rightNode.next;

  // 注意：切断链接
  pre.next = null;
  rightNode.next = null;

  // 第 4 步：同第 206 题，反转链表的子区间
  reverseLinkedList(leftNode);

  // 第 5 步：接回到原来的链表中
  pre.next = rightNode;
  leftNode.next = curr;
  return dummyNode.next;
};

const reverseLinkedList = (head) => {
  let pre = null;
  let cur = head;

  while (cur) {
    const next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
};

复杂度

• 时间复杂度：O(n)，其中 n 是链表总节点数。最坏情况下，需要遍历整个链表。
• 空间复杂度：O(1)。只使用到常数个变量。

24. 两两交换链表中的节点

题目

来源：力扣（LeetCode）24 两两交换链表中的节点 (opens new window)

难度：中等

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内

0 <= Node.val <= 100

思路

可以通过递归的方式实现两两交换链表中的节点。

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  if (head === null || head.next === null) {
    return head;
  }
  const newHead = head.next;
  head.next = swapPairs(newHead.next);
  newHead.next = head;
  return newHead;
};

复杂度

• 时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
• 空间复杂度：O(n)，其中 n 是链表的节点数量。

25. K 个一组翻转链表

题目

来源：力扣（LeetCode）25 K 个一组翻转链表 (opens new window)

难度：困难

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

- 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：head = [1], k = 1
输出：[1]

提示：

- 列表中节点的数量在范围 sz 内
- 1 <= sz <= 5000
- 0 <= Node.val <= 1000
- 1 <= k <= sz

思路

本题主要考查面试者设计的能力。

我们需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，否则不需要翻转。

接下来的问题就是如何翻转一个分组内的子链表。翻转一个链表并不难，过程可以参考「206. 反转链表」。但是对于一个子链表，除了翻转其本身之外，还需要将子链表的头部与上一个子链表连接，以及子链表的尾部与下一个子链表连接。如下图所示：

因此，在翻转子链表的时候，我们不仅需要子链表头节点 head，还需要有 head 的上一个节点 pre，以便翻转完后把子链表再接回 pre。

但是对于第一个子链表，它的头节点 head 前面是没有节点 pre 的。太麻烦了！难道只能特判了吗？答案是否定的。没有条件，我们就创造条件；没有节点，我们就创建一个节点。我们新建一个节点，把它接到链表的头部，让它作为 pre 的初始值，这样 head 前面就有了一个节点，我们就可以避开链表头部的边界条件。这么做还有一个好处，下面我们会看到。

反复移动指针 head 与 pre，对 head 所指向的子链表进行翻转，直到结尾，我们就得到了答案。下面我们该返回函数值了。

有的同学可能发现这又是一件麻烦事：链表翻转之后，链表的头节点发生了变化，那么应该返回哪个节点呢？照理来说，前 k 个节点翻转之后，链表的头节点应该是第 k 个节点。那么要在遍历过程中记录第 k 个节点吗？但是如果链表里面没有 k 个节点，答案又还是原来的头节点。我们又多了一大堆循环和判断要写，太崩溃了！

等等！还记得我们创建了节点 pre 吗？这个节点一开始被连接到了头节点的前面，而无论之后链表有没有翻转，它的 next 指针都会指向正确的头节点。那么我们只要返回它的下一个节点就好了。至此，问题解决。

代码

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const myReverse = (head, tail) => {
  let prev = tail.next;
  let p = head;
  while (prev !== tail) {
    const nex = p.next;
    p.next = prev;
    prev = p;
    p = nex;
  }
  return [tail, head];
};
var reverseKGroup = function(head, k) {
  const hair = new ListNode(0);
  hair.next = head;
  let pre = hair;

  while (head) {
    let tail = pre;
    // 查看剩余部分长度是否大于等于 k
    for (let i = 0; i < k; ++i) {
      tail = tail.next;
      if (!tail) {
        return hair.next;
      }
    }
    const nex = tail.next;
    [head, tail] = myReverse(head, tail);
    // 把子链表重新接回原链表
    pre.next = head;
    tail.next = nex;
    pre = tail;
    head = tail.next;
  }
  return hair.next;
};

复杂度

• 时间复杂度：O(n)，其中 n 为链表的长度。head 指针会在 O(n/k) 个节点上停留，每次停留需要进行一次 O(k) 的翻转操作。
• 空间复杂度：O(1)，我们只需要建立常数个变量。

参考文章

• 力扣 (LeetCode) - 题库 (opens new window)

感谢

如果本文对你有帮助 😘，就点个赞 👍 支持下吧！感谢阅读。