前端码农

Appearance

leetCode 刷题解析 ​

链表 ​

203.移除链表元素 ​

移除链表元素

思路 ​

  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.next;
  }
  return dummy.next;
};

160.相交链表 ​

相交链表

思路 ​

  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;

  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.反转链表|| ​

反转链表||

思路 ​

  • 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;
  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;
  }
  if (head.next !== null && head.next.next === null) {
    return head.val === head.next.val;
  }
  let slow = head; // 慢
  let fast = head; // 快
  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.删除排序链表中的重复元素|| ​

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

思路 ​

是使用哨兵节点（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.删除排序链表中的重复元素 ​

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

思路 ​

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

  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;
};