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

双指针 1

使用快慢指针

slow 指向当前准备检查的位置，fast 指向 slow 后面第一个可能不是 0 的位置

把为 0 的数据交换到后面

function moveZeroes(nums: number[]): void {
  let slow = 0 // 待处理的位置
  let fast = 1 // slow 后面已知的可能不是 0 的第一个位置

  // 遍历完所有的数据
  while (fast < nums.length) {
    // 当 slow 所在的位置是 0
    // 将 0 往后交换
    if (nums[slow] === 0) {
      // 找到后续第一个不为 0 的位置
      // 直接交换即可保证相对顺序不变
      while (nums[fast] === 0) {
        fast += 1
      }

      // 如果 right 超出了 nums
      // 说明后面的全是 0
      // 不需要处理了
      if (fast === nums.length) {
        break
      }

      // 交换
      nums[slow] = nums[fast]
      nums[fast] = 0
    }

    // 检查下一个位置
    // 因为两个指针当前位置都处理了
    // 所以都需要前进
    slow += 1
    fast += 1
  }
}

双指针 2

slow 指向已经处理过的尾部位置， fast 指向待处理的头部位置

把不为 0 的数据按照顺序放好

function moveZeroes(nums: number[]): void {
  let slow = 0 // 已经处理的尾部位置
  let fast = 0 // 待处理的头部位置

  // 遍历完所有的数据
  // 把不为 0 的数据按照顺序放好
  while (fast < nums.length) {
    // 当 fast 所在的位置不是 0
    // 说明符合结果放在 slow 的位置
    if (nums[fast] !== 0) {
      const temp = nums[slow]
      nums[slow] = nums[fast]
      nums[fast] = temp

      // 更新 slow
      slow += 1
    }

    // 检查下一个位置
    fast += 1
  }
}

双指针 3

利用去除 nums 的逻辑，然后再将去掉的值补充在末尾

function moveZeroes(nums: number[]): void {
  // 去除所有的 0
  const prev = removeElement(nums, 0)

  // 再把 0 补充到后面
  for (let i = prev; i < nums.length; i += 1) {
    nums[i] = 0
  }
}

/**
 * 参考 leetcode 27
 * 原地去除数组中等于 val 的元素，不影响顺序
 * 返回剩下的元素数量
 */
function removeElement(nums: number[], val: number): number {
  let slow = 0
  let fast = 0

  while (fast < nums.length) {
    if (nums[fast] !== val) {
      nums[slow] = nums[fast]

      slow += 1
    }

    fast += 1
  }

  return slow
}