链表中倒数第 k 个结点

题目描述

输入一个链表，输出该链表中倒数第 k 个结点。

思路

准备两个指针：p1和p2，初始时让p1和p2都指向链表头部，然后让p1不动，让p2往前走K步，这样p1和p2就相差了K个结点，然后让p1和p2同时向前走，当p2走到链表最后一个节点null时，此时p1所在的节点即为链表中倒数第 k 个结点，如图：

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindKthToTail(head, k) {
  let p1 = head;
  let p2 = head;
  // 让p1先走k步
  // 此处包含处理一种边界情况：当链表只有5个结点而要求倒数第6个结点时
  // 要求倒数第6个结点，则p1应向前走6步，而p1走到第5步时已经走到链表末尾null了，
  // 此时循环如果还未结束，那就说明是出现了这种边界情况，返回null即可
  for (let i = 0; i < k; i++) {
    if (p1) {
      p1 = p1.next;
    } else {
      return null;
    }
  }
  while (p1) {
    p1 = p1.next;
    p2 = p2.next;
  }
  return p2;
}