手帐 Blog

主题

06 · 同向双指针与快慢指针 ​

目标：掌握「读写指针」原地改数组，理解快慢指针判环。
精讲 283、26；141 环形链表给出可提交代码。

1. 为什么面试考 ​

  • 原地 修改数组是前端笔试常考点（省空间）。
  • 读写指针 = 一次遍历完成「筛选 / 压缩」。
  • 快慢指针是链表环检测的标准解法，一面爱问「为什么相遇一定在环内」。

2. 零基础概念 ​

2.1 同向双指针（读写指针） ​

两个指针 同方向 走，常见分工：

指针角色
read（快 / 读）扫描每个元素
write（慢 / 写）下一个要写入的位置
原: [2, 0, 1, 0, 3]
     w,r
        w  r
           w     r
              w        r
                 w           r  → 结果前缀 [2,1,3]

适用：删除重复、移动零、移除元素——保留的元素写到前面。

2.2 快慢指针 ​

指针步长
slow每次走 1 步
fast每次走 2 步

链表有环 → 快指针 eventually 追上慢指针（相遇）。
无环 → 快指针先到 null。

3. JS 模板 ​

3.1 读写指针（原地筛选） ​

javascript
function readWriteFilter(nums, keep) {
  let write = 0
  for (let read = 0; read < nums.length; read++) {
    if (keep(nums[read])) {
      nums[write] = nums[read]
      write++
    }
  }
  return write // 新有效长度
}

3.2 快慢指针（链表环） ​

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

4. 精讲 · 283 移动零 ​

题意：把 0 移到末尾，保持非零元素相对顺序。原地。

套路：write 写下所有非零；扫完后把 [write, n) 填 0。

javascript
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place.
 */
var moveZeroes = function (nums) {
  let write = 0

  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      nums[write] = nums[read]
      write++
    }
  }

  for (let i = write; i < nums.length; i++) {
    nums[i] = 0
  }
}

口述：读指针看每个数；非零就写到 write 再 write++；最后补零。

5. 精讲 · 26 删除有序数组中的重复项 ​

题意：升序数组，原地 去重，返回新长度。前 k 个是不重复元素。

套路：write 指向「已去重区间的最后一个」；read 遇到新值就 write++ 并写入。

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  if (nums.length === 0) return 0

  let write = 0

  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write]) {
      write++
      nums[write] = nums[read]
    }
  }

  return write + 1
}

边界：空数组返回 0；单元素返回 1。

对比 283：283 是「保留某种值」；26 是「相邻相同就跳过」。

6. 精讲 · 141 环形链表（快慢指针） ​

题意：判断链表是否有环。

javascript
/**
 * 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}
 */
var hasCycle = function (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
}

为什么相遇说明有环？
有环时快指针在环里「追」慢指针，步长差 1，一定会在环内某点相遇。
无环时快指针先走到 null。

进阶 142（可选）：相遇后，一个指针回到 head，两个都每次走 1 步，再相遇处就是环入口——本篇知道 141 即可。

7. 练习清单 ​

题号名称难度备注
283移动零Easy本篇已精讲
26删除有序数组重复项Easy本篇已精讲
27移除元素Easy读写：保留 ≠ val
80删除重复项 IIMedium最多保留 2 个，write 逻辑微调
141环形链表Easy本篇已精讲
142环形链表 IIMedium找环入口

8. 今日验收 ​

  • [ ] 默写 283：先写非零，再补零
  • [ ] 默写 26：write 初始 0，read 从 1 开始
  • [ ] 能画 141 快慢指针在环里相遇的示意
  • [ ] LeetCode 提交 283、26、141 至少各 1 次 AC

9. 可选 · 记忆唤醒 ​

读写：read 扫全程，满足条件就 nums[write]=...; write++
283：非零前移，尾部填 0
26：有序相邻相同 → read 跳过，新值 write++
快慢：slow 走 1，fast 走 2，相遇即有环

下一步 ​

→ 07 · 滑动窗口