# 链表中倒数第 k 个结点

# 题目描述

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

# 思路

准备两个指针:p1p2,初始时让p1p2都指向链表头部,然后让p1不动,让p2往前走K步,这样p1p2就相差了K个结点,然后让p1p2同时向前走,当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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24