面试题 02.02. 返回倒数第 k 个结点

双指针

一个用于遍历，一个用于记录当前的目标结点

function kthToLast(head: ListNode | null, k: number): number {
  // 思路如下
  // 根据 k 和 n，可以反推出来当第一次 k == n 的时候，头结点就是 lastK
  // 之后每次遍历的时候只需要同时移动 lastK 即可

  let lastK // 记录倒数第 k 个结点的数据
  let p = head // 当前遍历到的结点
  let len = 0 // 当前链表的长度

  // 遍历链表
  while (p) {
    // 每次遍历将长度增加
    len += 1

    // 当长度等于 k 的时候，初始化 lastK
    if (len === k) {
      lastK = head
    } else if (len > k) {
    // 如果 laskK 存在，同步更新
      lastK = lastK.next
    }

    // 进行下一场遍历
    p = p.next
  }

  return lastK.val
}

双指针2

可以先步进 k 个结点，然后同步遍历双指针即可

function kthToLast(head: ListNode | null, k: number): number {
  let p = head // 当前遍历到的结点

  // 因为题目保证了 k 有效
  // 可以先遍历到指定位置
  for (let i = 0; i < k; i += 1) {
    p = p.next
  }

  // 初始化 lastK
  let lastK = head

  // 接着遍历后续结点
  while (p) {
    // 同步更新 lastK 和 p
    lastK = lastK.next

    // 进行下一场遍历
    p = p.next
  }

  return lastK.val
}