前端码农

Appearance

leetCode 刷题解析 ​

203.移除链表元素 ​

力扣题目链接

题目描述 ​

  • 删除链表中等于给定值 val 的所有节点。

思路 ​

  1. 虚拟头节点（Dummy Node）：
    • 创建虚拟头节点 dummy，其 next 指向原链表头节点。这样即使头节点被删除，也能统一处理所有节点。
  2. 双指针遍历：
    • pre 指针：指向当前节点的前驱节点，初始指向 dummy。
    • cur 指针：遍历链表，初始指向原头节点。
  3. 删除逻辑：
    • 若 cur.val === val：跳过当前节点（pre.next = cur.next），cur 后移。
    • 若 cur.val !== val：pre 和 cur 同时后移。
  4. 返回结果：返回 dummy.next（即新链表的头节点）。

关键点解析 ​

  1. 虚拟头节点：
    • 避免单独处理头节点被删除的边界情况。
  2. 双指针操作：
    • pre 始终指向当前节点的前驱节点，确保删除操作时链表不断裂。
    • 删除节点时仅更新指针（pre.next），不移动 pre，以应对连续删除场景。
  3. 时间复杂度：O(n)，空间复杂度：O(1)。

示例演示 ​

以链表 1 → 2 → 6 → 3 → 4 → 5 → 6 → null 删除 6 为例：

  1. 初始化：dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
  2. 删除第一个 6：
    • pre 停在 2，cur 指向第一个 6。
    • 执行 pre.next = cur.next（2 直接指向 3）。
  3. 删除第二个 6：
    • pre 仍为 2，cur 指向末尾 6。
    • 执行 pre.next = cur.next（5 的 next 置为 null）。
  4. 结果：1 → 2 → 3 → 4 → 5。

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
const removeElements = function (head, val) {
  if (head === null) return null;
  // 创建虚拟头节点
  let dummy = {
    next: head,
  };
  // 双指针遍历
  let pre = dummy; // 前驱节点
  let cur = head; // 当前节点
  while (cur) {
    if (cur.val === val) {
      // 如果相等，前驱跳过当前节点
      pre.next = cur.next;
    } else {
      // cur节奏比pre快，所以直接指向cur
      pre = cur;
    }
    // cur后移
    cur = cur.next;
  }
  return dummy.next;
};

160.相交链表 ​

力扣题目链接

题目描述 ​

  • 找到两个单链表相交的起始节点。如果两个链表没有交点，则返回 null。

思路 ​

  1. 双指针法：
    • 初始化两个指针 pA 和 pB，分别指向链表 A 和 B 的头节点。
    • 遍历链表，当指针到达链表末尾时，跳到另一个链表的头节点继续遍历。
    • 当两个指针相遇时，即为相交节点。
  2. 原理：
    • 假设链表 A 的长度为 m，链表 B 的长度为 n，相交部分长度为 c。

数学解释：操场比喻与路径平衡原理 ​

  • A 操场：总长 40 米（20 米独有跑道 + 20 米共享跑道）
  • B 操场：总长 50 米（30 米独有跑道 + 20 米共享跑道）

双指针运动轨迹 ​

  • A,B 跑 70 米处相遇

  1. 指针 A 路径：

    • 先跑完 A 操场独有 20 米
    • 再跑完 B 操场独有 30 米
    • 最后进入共享跑道
    • 总路程 = 20 + 30 + 20 = 70 米

  2. 指针 B 路径：

    • 先跑完 B 操场独有 30 米
    • 再跑完 A 操场独有 20 米
    • 最后进入共享跑道
    • 总路程 = 30 + 20 + 20 = 70 米

示例演示 ​

场景 1：相交链表

text
链表 A：`4 → 1 → 8 → 4 → 5`
链表 B：`5 → 6 → 1 → 8 → 4 → 5`（相交节点 `8`）
指针 A 路径：4→1→8→4→5→5→6→1→[8]
指针 B 路径：5→6→1→8→4→5→4→1→[8]
                             ↑ 相遇点

场景 2：不相交链表

text
链表 A：`2 → 6 → 4`
链表 B：`1 → 5`
指针 A 路径：2→6→4→1→5→null
指针 B 路径：1→5→2→6→4→null
                        ↑ 同时为 null

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getIntersectionNode = function (headA, headB) {
  // 边界条件
  if (headA === null || headB === null) return null;
  let pointA = headA;
  let pointB = headB;
  // 如果两个链表相交，则两个指针一定会在相交节点处相遇
  // 如果两个链表不相交，则两个指针最终会同时到达链表末尾（null）
  while (pointA !== pointB) {
    //  if (pointA === null) {
    //    pointA = headB;
    //  } else {
    //    pointA = pointA.next;
    //  }
    //  if (pointB === null) {
    //    pointB = headA;
    //  } else {
    //    pointB = pointB.next;
    //  }
    pointA = pointA ? pointA.next : headB;
    pointB = pointB ? pointB.next : headA;
  }
  return pointA;
};

206.反转链表 ​

力扣题目链接

题目描述 ​

  • 反转一个单链表。

思路 ​

  • 通过改变节点指针方向实现链表反转。使用双指针遍历链表，逐个反转节点指向。

  1. 初始化指针：

    • prev：指向当前节点的前一个节点（初始为 null）
    • curr：指向当前遍历的节点（初始为头节点 head）

  2. 遍历链表：

    • 保存当前节点的下一个节点nextNode（防止断链）
    • 将当前节点的 next 指针指向 prev（反转指针方向）
    • 将 prev 移动到 curr 位置
    • 将 curr 移动到下一个节点(nextNode)

  3. 终止条件：

    • 当 curr 变为 null 时停止遍历
    • 此时 prev 指向新链表的头节点

示例演示 ​

以链表 1 → 2 → 3 → 4 → 5 → null 为例：

  1. 初始状态：prev = null, curr = 1
  2. 第一步：
    • 保存 next = 2
    • 反转：1.next = null → 1 → null
    • 移动指针：prev = 1, curr = 2
  3. 第二步：
    • 保存 next = 3
    • 反转：2.next = 1 → 2 → 1 → null
    • 移动指针：prev = 2, curr = 3
  4. 重复直至结束：
    • 最终得到 5 → 4 → 3 → 2 → 1 → null
    • 返回 prev = 5 作为新头节点

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseList = function (head) {
  if (head === null) return null;
  // 初始化指针
  let pre = null;
  let cur = head;
  while (cur) {
    // 保存当前节点的下一个节点
    let next = cur.next;
    // 反转指针方向
    cur.next = pre;
    // 移动指针
    pre = cur;
    // 移动到下一个节点
    cur = next;
  }
  return pre;
};

328.奇偶链表 ​

力扣题目链接

题目描述 ​

  • 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

思路 ​

  1. 分离奇偶节点：
    • 使用两个指针 odd 和 even 分别遍历奇数节点和偶数节点。
    • 奇数节点链：从头节点（节点 1）开始，连接所有奇数位置的节点。
    • 偶数节点链：从第二个节点（节点 2）开始，连接所有偶数位置的节点。
  2. 合并链表：
    • 遍历结束后，将奇数链表的尾部连接到偶数链表的头部。

算法步骤 ​

  1. 边界处理：若链表为空、只有一个节点或只有两个节点，直接返回 head。
  2. 初始化指针：
    • odd 指向头节点（第一个奇数节点）。
    • even 指向第二个节点（第一个偶数节点），并保存 evenHead 作为偶数链表的头。
  3. 遍历链表：
    • 将 odd.next 指向 even.next（下一个奇数节点）。
    • 移动 odd 到下一个奇数节点。
    • 将 even.next 指向 odd.next（下一个偶数节点）。
    • 移动 even 到下一个偶数节点。
  4. 合并链表：将奇数链表的尾部（odd）连接到偶数链表的头部（evenHead）。

示例演示 ​

示例：1 → 2 → 3 → 4 → 5

  1. 分离奇偶链：
    • 奇数链：1 → 3 → 5
    • 偶数链：2 → 4
  2. 合并：将奇数链尾部（5）连接偶数链头部（2）
  3. 结果：1 → 3 → 5 → 2 → 4
  • 双指针 odd（奇数节点）和 even（偶数节点）同步移动
  • 每次操作：
    1. odd.next = even.next（链接下一个奇数节点）
    2. even.next = odd.next（链接下一个偶数节点）
  • 最后用 evenHead 连接两个链表

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function (head) {
  // 边界条件
  if (head === null || head.next === null || head.next.next === null)
    return head;
  let odd = head; // 奇数节点链表头
  let even = head.next; // 偶数节点链表头
  let evenHead = even; // 保存偶数节点链表头
  // 如果偶数，后面还有节点(奇数)
  while (even && even.next) {
    // 奇数&偶数节点连接
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }
  // 奇数节点链表尾部连接偶数节点链表头部
  odd.next = evenHead;
  return head;
};

92.反转链表|| ​

力扣题目链接

题目描述 ​

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

思路 ​

  • 1、构建⼀个虚拟节点，让它指向原链表的头节点。
  • 2、设置两个指针，pre 指针指向以虚拟头节点为链表的头部位置，cur 指针指向原链表的头部位置。
  • 3、让着两个指针向前移动，直到 pre 指向了第⼀个要反转的节点的前⾯那个节点，⽽ cur 指向了第⼀个要反转的节点。
  • 4、开始指向翻转操作
    • 1）、设置临时变量 node，node 是 cur 的 next 位置，保存当前需要翻转节点的后⾯的节点，我们需要交换 node 和 cur
    • 2）、让 cur 的 next 位置变成 node 的下⼀个节点
    • 3）、让 node 的 next 位置变成 cur
    • 4）、让 pre 的 next 位置变成 node

示例演示 ​

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
const reverseBetween = function (head, left, right) {
  // 边界条件
  if (head === null) return null;
  // 创建一个虚拟头节点
  let dummy = {
    next: head,
  };
  // 双两个指针
  let pre = dummy;
  let cur = head;
  // 定位到left位置
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next; // 因为需要反转，所以需要来的需要反转的前一个节点
    cur = cur.next;
  }
  // 反转链表
  for (let index = 0; index < right - left; index++) {
    let node = cur.next; // 保存当前节点的下一个节点
    cur.next = node.next; // 当前节点指向下一个节点的下一个节点
    node.next = pre.next; // 下一个节点指向当前节点的下一个节点
    pre.next = node; // 当前节点指向下一个节点
  }
  return dummy.next;
};

234.回文链表 ​

力扣题目链接

题目描述 ​

  • 请判断一个链表是否为回文链表。(正序和倒序读值都一样)

思路 ​

使用快慢指针法解决回文链表问题：

  1. 快慢指针定位中点：快指针每次走两步，慢指针每次走一步
  2. 反转后半部分：从慢指针位置开始反转链表后半部分
  3. 比较前后两半：比较前半部分和反转后的后半部分是否相同
  4. 恢复链表结构（可选）：如果需要保持原链表结构，可以再次反转恢复

示例演示 ​

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const isPalindrome = function (head) {
  // 空链表和单节点链表是回文链表
  if (head === null) {
    return true;
  }
  // 2个节点链表，判断是否相等
  if (head.next !== null && head.next.next === null) {
    return head.val === head.next.val;
  }
  let slow = head; // 慢
  let fast = head; // 快
  // 循环结束后，slow指向中间节点，fast指向末尾节点
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let leftHead = head; // 前半部分链表头
  let rightHead = reverseList(slow.next); // 后半部分链表头(反转之后的)

  // 循环对比
  while (rightHead) {
    if (leftHead.val !== rightHead.val) {
      return false;
    }
    leftHead = leftHead.next;
    rightHead = rightHead.next;
  }
  return true;
};

const reverseList = (head) => {
  let pre = null;
  let cur = head;
  while (cur) {
    let next = cur.next;
    cur.next = pre;
    per = cur;
    cur = next;
  }
  return pre;
};

82.删除排序链表中的重复元素|| ​

力扣题目链接

题目描述 ​

  • 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

思路 ​

是使用哨兵节点（dummy node） 处理头节点可能被删除的情况，通过双指针遍历识别并删除重复元素：

  1. 哨兵节点：创建一个指向头节点的哨兵节点，解决头节点被删除时的边界问题
  2. 双指针遍历：
    • 使用 cur 指针从哨兵节点开始遍历
    • 当检测到重复时（cur.next.val === cur.next.next.val）：
      • 记录重复值 x
      • 循环删除所有值为 x 的节点
    • 当无重复时，正常移动指针
  3. 终止条件：当后续不足两个节点时停止检测

示例演示 ​

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const deleteDuplicates = function (head) {
  // 边界条件
  if (head === null) return null;
  // 创建一个虚拟头节点
  let dummy = {
    next: head,
  };
  // 当前节点,从虚拟头节点开始
  let cur = dummy;

  while (cur.next && cur.next.next) {
    // 如果当前节点的下一个节点和下下个节点值相等,则说明有重复节点
    // 删除重复节点
    if (cur.next.val === cur.next.next.val) {
      let x = cur.next.val;
      while (cur.next && cur.next.val === x) {
        cur.next = cur.next.next;
      }
    } else {
      // 否则，当前节点后移
      cur = cur.next;
    }
  }
  return dummy.next;
};

83.删除排序链表中的重复元素 ​

力扣题目链接

题目描述 ​

  • 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

思路 ​

题目要求删除排序链表中的重复元素，保留每个元素的第一次出现。由于链表已排序，重复元素必然相邻，因此只需遍历一次链表：

  1. 单指针遍历：使用指针 cur 从链表头开始遍历
  2. 重复检测：比较当前节点与下一节点的值
    • 若相等：跳过下一节点（cur.next = cur.next.next）
    • 若不相等：移动指针到下一节点
  3. 终止条件：当当前节点或下一节点为空时停止

示例演示 ​

示例演示 ​

以输入链表 [1, 1, 2, 3, 3] 为例：

  1. 第一轮：1 与 1 重复 → 跳过第二个 1，链表变为 [1, 2, 3, 3]
  2. 第二轮：1 与 2 不重复 → 移动指针到 2
  3. 第三轮：2 与 3 不重复 → 移动指针到 3
  4. 第四轮：3 与 3 重复 → 跳过第二个 3，链表变为 [1, 2, 3]
  5. 返回结果：[1, 2, 3]

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
  // 边界条件
  if (head === null) return null;
  // 当从节点开始
  let cur = head;
  // 如果有下一个节点，循环
  while (cur && cur.next) {
    // 如果当前节点和下一个节点值相等，跳过下一个节点
    if (cur.val == cur.next.val) {
      cur.next = cur.next.next;
    } else {
      // 否则，移动指针到下一个节点
      cur = cur.next;
    }
  }
  return head;
};

86.分割链表 ​

力扣题目链接

题目描述 ​

  • 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

思路 ​

  1. 创建两个虚拟（Dummy Nodes）：

    • minHead：用于链接所有小于 x 的节点。
    • maxHead：用于链接所有大于等于 x 的节点。

  2. 遍历原链表：

    • 若当前节点值 < x，将其链接到 minHead 的链表末尾。
    • 若当前节点值 >= x，将其链接到 maxHead 的链表末尾。

  3. 合并链表：

    • 将 minHead 链表的末尾指向 maxHead 链表的头节点（跳过哑节点）。
    • 将 maxHead 链表的末尾节点的 next 置为 null（避免循环）。

  4. 返回结果：

    • 返回 minHead.next（跳过哑节点）。

示例演示 ​

以输入 head = [1,4,3,2,5,2], x = 3 为例：

  1. 初始化两个虚拟节点：minHead 和 maxHead。
  2. 遍历链表：
    • 1 < 3 → 加入 min 链表：minHead → 1
    • 4 >= 3 → 加入 max 链表：maxHead → 4
    • 3 >= 3 → 加入 max 链表：maxHead → 4 → 3
    • 2 < 3 → 加入 min 链表：minHead → 1 → 2
    • 5 >= 3 → 加入 max 链表：maxHead → 4 → 3 → 5
    • 2 < 3 → 加入 min 链表：minHead → 1 → 2 → 2
  3. 合并链表：
    • min 链表末尾（节点 2）指向 max 链表头（节点 4）：1 → 2 → 2 → 4 → 3 → 5
    • 将 max 链表末尾（节点 5）的 next 置为 null。
  4. 返回 minHead.next（即节点 1）。

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
const partition = function (head, x) {
  if (head === null) return null;
  let minHead = {
    next: null,
  };
  let min = minHead;
  let maxHead = {
    next: null,
  };
  let max = maxHead;
  let cur = head;
  while (cur) {
    if (cur.val < x) {
      min.next = cur;
      min = min.next;
    } else {
      max.next = cur;
      max = max.next;
    }
    cur = cur.next;
  }
  // 后面可能有小于x的节点，所以需要断开
  max.next = null;
  min.next = maxHead.next;
  return minHead.next;
};

141.环形链表 ​

力扣题目链接

题目描述 ​

  • 给定一个链表，判断链表中是否有环。

思路 ​

快慢指针法（Floyd 判圈算法）：

  1. 使用两个指针：slow（每次移动 1 步）和 fast（每次移动 2 步）。
  2. 如果链表有环，快指针最终会追上慢指针（相遇）。
  3. 如果链表无环，快指针会先到达链表尾部（fast 或 fast.next 为 null）。

示例演示 ​

  1. 有环链表 1 → 2 → 3 → 4 → 5 → 2（环入口在 2）：

    • 初始：slow=1, fast=1
    • 步骤 1：slow=2, fast=3
    • 步骤 2：slow=3, fast=5
    • 步骤 3：slow=4, fast=3（5→2→3）
    • 步骤 4：slow=5, fast=5（相遇 → 返回 true）

  2. 无环链表 1 → 2 → 3 → 4 → 5 → null：

    • 初始：slow=1, fast=1
    • 步骤 1：slow=2, fast=3
    • 步骤 2：slow=3, fast=5（fast.next=null → 退出循环 → 返回 false）

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = function (head) {
  if (head === null) return false; // 空链表直接返回false
  let slow = head;
  let fast = head;

  // 循环条件确保快指针能安全移动两步
  while (fast.next && fast.next.next) {
    slow = slow.next; // 慢指针移动1步
    fast = fast.next.next; // 快指针移动2步
    if (slow === fast) {
      // 相遇说明有环
      return true;
    }
  }
  return false; // 快指针到达尾部，无环
};

142.环形链表|| ​

力扣题目链接

题目描述 ​

  • 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

思路 ​

快慢指针法（Floyd 判圈算法扩展）：

  1. 阶段一：检测链表是否有环
    • 使用快指针（每次 2 步）和慢指针（每次 1 步）遍历链表
    • 若快慢指针相遇，说明链表有环
  2. 阶段二：定位环入口节点
    • 将其中一个指针移回链表头部
    • 两个指针以相同速度（每次 1 步）移动
    • 再次相遇的节点即为环入口节点

示例演示 ​

有环链表 1 → 2 → 3 → 4 → 5 → 2（环入口为节点 2）：

  1. 阶段一：快慢指针移动
    • 初始：slow=1, fast=1
    • 第 1 步：slow=2, fast=3
    • 第 2 步：slow=3, fast=5
    • 第 3 步：slow=4, fast=3（5→2→3）
    • 第 4 步：slow=5, fast=5（相遇）
  2. 阶段二：定位环入口
    • index1 从头节点 1 开始
    • index2 从相遇点 5 开始
    • 第 1 步：index1=2, index2=2（相遇）
    • 返回节点 2

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const detectCycle = function (head) {
  if (head === null) return null;
  let slow = head;
  let fast = head;

  // 阶段一：检测是否有环
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;

    // 检测到环
    if (slow === fast) {
      // 阶段二：定位环入口
      let index1 = head; // 指针1从头节点出发
      let index2 = fast; // 指针2从相遇点出发

      // 两指针同步移动直到相遇
      while (index1 !== index2) {
        index1 = index1.next;
        index2 = index2.next;
      }
      return index1; // 相遇点即为环入口
    }
  }
  return null; // 无环
};

21.合并 2 个有序链表 ​

力扣题目链接

题目描述 ​

  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路 ​

迭代法：

  1. 边界处理：
    • 若两链表均为空 → 返回 null
    • 若一链表为空 → 返回另一链表
  2. 虚拟头节点：
    • 创建 dummy 节点简化边界处理
    • 用 head 指针追踪合并链表的尾部
  3. 双指针比较：
    • 同时遍历两链表
    • 比较节点值，将较小值接入合并链表
    • 移动较小值所在链表的指针
  4. 处理剩余节点：
    • 当一链表遍历完，将另一链表剩余部分直接接入
  5. 返回结果：
    • 返回 dummy.next（真实头节点）

示例演示 ​

输入：
list1 = 1 → 3 → 5
list2 = 2 → 4 → 6

合并过程：

  1. 比较 1 vs 2 → 接入 1：
    合并链表：dummy → 1
    list1 → 3, list2 → 2
  2. 比较 3 vs 2 → 接入 2：
    合并链表：dummy → 1 → 2
    list1 → 3, list2 → 4
  3. 比较 3 vs 4 → 接入 3：
    合并链表：dummy → 1 → 2 → 3
    list1 → 5, list2 → 4
  4. 比较 5 vs 4 → 接入 4：
    合并链表：dummy → 1 → 2 → 3 → 4
    list1 → 5, list2 → 6
  5. 比较 5 vs 6 → 接入 5：
    合并链表：dummy → 1 → 2 → 3 → 4 → 5
    list1 → null
  6. 接入 list2 剩余节点 6：
    合并链表：dummy → 1 → 2 → 3 → 4 → 5 → 6

输出：1 → 2 → 3 → 4 → 5 → 6

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  // 边界处理
  if (list1 === null && list2 === null) return null;
  // 若一链表为空 → 返回另一链表
  if (list1 === null) return list2;
  if (list2 === null) return list1;
  // 虚拟头节点
  let dummy = {
    next: null,
  };
  let head = dummy;
  /// 双指针比较
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      head.next = list1;
      list1 = list1.next;
    } else {
      head.next = list2;
      list2 = list2.next;
    }
    // 移动合并链表尾部指针
    head = head.next;
  }
  // 直接连接剩余链表
  head.next = list1 || list2;
  return dummy.next;
};

138.随机链表的复制 ​

力扣题目链接

题目描述 ​

  • 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或 null。

思路 ​

复制带随机指针的链表需要解决的关键问题是：当复制节点时，随机指针指向的节点可能尚未创建。使用哈希表（Map）存储原节点到新节点的映射，通过两次遍历解决：

  1. 第一次遍历：创建所有新节点，建立原节点到新节点的映射（包括 null 映射）
  2. 第二次遍历：根据映射关系，设置新节点的 next 和 random 指针

示例演示 ​

代码实现 ​

javascript
/**
 * // Definition for a _Node.
 * function _Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
var copyRandomList = function (head) {
  if (head === null) return null;

  // 创建哈希表并处理null映射
  const map = new Map();
  map.set(null, null); // 关键：确保null映射到null

  // 第一次遍历：创建所有新节点
  let cur = head;
  while (cur) {
    map.set(cur, new _Node(cur.val, null, null));
    cur = cur.next;
  }

  // 第二次遍历：获取所以的新节点映射
  cur = head;
  while (cur) {
    const newNode = map.get(cur);
    newNode.next = map.get(cur.next);
    newNode.random = map.get(cur.random);
    cur = cur.next;
  }

  return map.get(head);
};

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

力扣题目链接

题目描述 ​

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

思路 ​

要两两交换链表中的节点，可以通过迭代的方式实现。使用一个虚拟节点（dummy node）简化头节点交换的操作。遍历链表时，每次处理两个相邻节点：

  1. 保存当前节点的下一个节点（第一个节点）和下一个节点的下下个节点（下一对的起始节点）。
  2. 将当前节点的下一个节点指向第二个节点。
  3. 将第二个节点的下一个节点指向第一个节点。
  4. 将第一个节点的下一个节点指向保存的下一对起始节点。
  5. 移动当前指针到交换后的第一个节点位置，继续下一轮交换。

示例演示 ​

以链表 1->2->3->4 为例：

  1. 初始状态：dummy -> 1 -> 2 -> 3 -> 4
  2. 第一轮交换（处理节点 1 和 2）：
    • 当前节点为 dummy，交换后：dummy -> 2 -> 1 -> 3 -> 4
    • 移动当前节点到 1（交换后的第二个节点）
  3. 第二轮交换（处理节点 3 和 4）：
    • 交换后：dummy -> 2 -> 1 -> 4 -> 3
    • 移动当前节点到 3
  4. 最终结果：2->1->4->3

代码实现 ​

js
const swapPairs = function (head) {
  if (head === null) return null;
  // 创建虚拟节点(需要交换节点的前一个节点)
  let dummy = { next: head };
  // 当前指针
  let cur = dummy;
  // 迭代，如果当前节点和下一个节点都存在，则进行交换
  while (cur.next && cur.next.next) {
    let temp1 = cur.next;
    let temp2 = cur.next.next.next;
    cur.next = cur.next.next;
    cur.next.next = temp1;
    temp1.next = temp2;
    cur = temp1; // cur指针移动到下一个节点(需要交换节点的前一个节点)
  }
  return dummy.next;
};

61.旋转链表 ​

力扣题目链接

题目描述 ​

  • 给你一个链表的头节点 head，旋转链表，将链表每个节点向右移动 k 个位置。

思路 ​

示例演示 ​

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const rotateRight = function (head, k) {
  if (head === null || k === 0) return head;
  let len = 1;
  let temp = head;
  while (temp.next) {
    temp = temp.next;
    len++;
  }
  k = k % len; // 处理k大于链表长度的情况
  let slow = head;
  let fast = head;
  for (let i = 0; i < k; i++) {
    slow = slow.next;
  }
  while (slow.next) {
    slow = slow.next;
    fast = fast.next;
  }
  slow.next = head;
  let newHead = fast.next;
  fast.next = null;
  return newHead;
};

143.重排链表 ​

力扣题目链接

题目描述 ​

  • 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
  • 1->2->3->4->5 重排为 1->5->2->4->3

思路 ​

重排链表的关键是将链表分成两半，反转后半部分，然后交替合并。具体步骤如下：

  1. 快慢指针找中点：

    • 使用快慢指针技巧找到链表中点（慢指针每次走 1 步，快指针每次走 2 步）
    • 当快指针到达末尾时，慢指针正好指向中点（奇数链表指向中间节点，偶数链表指向前半部分末尾）

  2. 断开并反转后半部分：

    • 将链表从中点后断开，形成两个独立链表
    • 反转后半部分链表（使最后节点变为头节点）

  3. 交替合并链表：

    • 将前半部分和反转后的后半部分交替合并
    • 每次取前半部分一个节点和后半部分一个节点连接

示例演示 ​

示例 1：1->2->3->4

  1. 找中点：slow 停在 2（fast 停在 3）
  2. 断开：前半部分 1->2，后半部分 3->4
  3. 反转后半部分：4->3
  4. 交替合并：
    • 1->4->2->3

示例 2：1->2->3->4->5

  1. 找中点：slow 停在 3（fast 停在 5）
  2. 断开：前半部分 1->2->3，后半部分 4->5
  3. 反转后半部分：5->4
  4. 交替合并：
    • 1->5->2->4->3

代码实现 ​

javascript
const reorderList = function (head) {
  // 空链表或单节点直接返回
  if (!head || !head.next) return;

  // 1. 快慢指针找中点（slow停在前半部末尾）
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. 断开链表并反转后半部分
  let secondHalf = slow.next; // 后半部分头节点
  slow.next = null; // 关键：断开前后链表

  // 反转后半部分
  let prev = null;
  let curr = secondHalf;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  secondHalf = prev; // prev成为反转后的头节点

  // 3. 交替合并两个链表
  let first = head;
  let second = secondHalf;
  while (first && second) {
    // 保存下一节点
    const firstNext = first.next;
    const secondNext = second.next;

    // 交替连接节点
    first.next = second;
    second.next = firstNext;

    // 移动指针
    first = firstNext;
    second = secondNext;
  }
};

876.链表的中间节点 ​

力扣题目链接

题目描述 ​

  • 给定一个链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

思路 ​

寻找链表中间节点的标准解法是使用快慢指针技巧：

  1. 快指针每次移动两步
  2. 慢指针每次移动一步
  3. 当快指针到达链表末尾时，慢指针正好位于中间位置

关键点：

  • 链表节点数为奇数时，慢指针停在唯一中间节点
  • 链表节点数为偶数时，慢指针停在第二个中间节点（题目要求）

示例演示 ​

示例 1：奇数节点 (1→2→3→4→5)

步骤   slow    fast
0:     1       1
1:     2       3
2:     3       5 → 停止（fast.next=null）
返回节点3

示例 2：偶数节点 (1→2→3→4→5→6)

步骤   slow    fast
0:     1       1
1:     2       3
2:     3       5
3:     4       null → 停止
返回节点4

代码实现 ​

javascript
const middleNode = function (head) {
  let slow = head;
  let fast = head;

  // 快指针每次移动两步，慢指针每次移动一步
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
};

19.删除链表的倒数第 N 个节点 ​

力扣题目链接

题目描述 ​

  • 给定一个链表，删除链表的倒数第 n 个节点，并返回链表的头节点。

思路 ​

使用双指针（快慢指针）技巧：

  1. 虚拟节点（Dummy Node）：创建虚拟节点指向头节点，简化删除头节点的边界处理
  2. 快指针先走：快指针先向前移动 n+1 步，使快慢指针间距为 n+1
  3. 同步移动：同时移动快慢指针，当快指针到达尾部时，慢指针正好停在待删除节点的前驱位置
  4. 删除节点：修改慢指针的 next 指向，跳过待删除节点

示例演示 ​

以 head = [1,2,3,4,5], n = 2 为例：

  1. 初始状态：dummy(0) → 1 → 2 → 3 → 4 → 5
  2. 快指针前进 3 步：fast 停在 3，slow 停在 dummy
  3. 同步移动：
    • fast=4, slow=1
    • fast=5, slow=2
    • fast=null, slow=3（此时 slow 停在待删除节点 4 的前驱）
  4. 删除节点：slow.next = slow.next.next → 链表变为 [1,2,3,5]

代码实现 ​

javascript
var removeNthFromEnd = function (head, n) {
  // 创建虚拟节点
  const dummy = {
    next: head,
  };
  let fast = dummy,
    slow = dummy;

  // 快指针先走 n+1 步
  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }

  // 同步移动双指针
  while (fast) {
    fast = fast.next;
    slow = slow.next;
  }

  // 删除目标节点
  slow.next = slow.next.next;
  return dummy.next; // 返回新头节点
};

704.二分查找 ​

力扣题目链接

题目描述 ​

  • 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

思路 ​

示例演示 ​

代码实现 ​

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let l = 0;
  let r = nums.length - 1;
  while (l <= r) {
    let m = (l + r) >> 1;
    if (nums[m] > target) {
      r = m - 1;
    } else if (nums[m] < target) {
      l = m + 1;
    } else {
      return m;
    }
  }
  return -1;
};

27.移除元素 ​

力扣题目链接

题目描述 ​

  • 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

思路 ​

示例演示 ​

代码实现 ​

js
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== val) {
      nums[slow++] = nums[fast];
    }
  }
  return slow;
};

977.有序数组的平方 ​

力扣题目链接

题目描述 ​

  • 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路 ​

示例演示 ​

代码实现 ​

js
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  let n = nums.length;
  let res = new Array(n).fill(0);

  let l = 0;
  let r = n - 1;
  let k = n - 1;
  while (l <= r) {
    let left = nums[l] * nums[l];
    let right = nums[r] * nums[r];
    if (left > right) {
      res[k--] = left;
      l++;
    } else {
      res[k--] = right;
      r--;
    }
  }
  return res;
};

209.长度最小的子数组 ​

力扣题目链接

题目描述 ​

  • 给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路 ​

示例演示 ​

代码实现 ​

js
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
const minSubArrayLen = function (target, nums) {
  let sum = 0;
  let left = 0;
  let result = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      result = Math.min(result, right - left + 1);
      sum -= nums[left++];
    }
  }
  return result === Infinity ? 0 : result;
};

3. 无重复字符的最长子串 ​

力扣题目链接

题目描述 ​

  • 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

思路 ​

示例演示 ​

代码实现 ​

js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let left = 0;
  let result = 0;
  let charSet = new Set();

  for (let right = 0; right < s.length; right++) {
    let str = s[right];
    while (charSet.has(str)) {
      charSet.delete(s[left++]);
    }
    result = Math.max(result, right - left + 1);
    charSet.add(str);
  }
  return result;
};