前言
给定一个单向链表的头节点，如何获取该链表中倒数第K个节点（从1开始计数）？本文将带着大家一起解决这个问题，欢迎各位感兴趣的开发者阅读本文。
思路分析
我们通过一个例子来做进一步的分析：
-
准备一个链表，它有6个节点，从头节点开始，其值依次为：1、3、5、9、15、21
-
获取该链表的倒数第3个节点
遍历两次链表
根据单向链表的定义，我们可知：想要获取它的某个节点，只能从头节点开始顺着其指针往后查找。假设整个链表有n个节点，那么倒数第K个节点就是从头节点开始的第n-K+1个节点。如果我们能够得到节点数n，那么只需要从头节点开始往后走n-k+1步就可以了。想要得到节点数n，就需要定义一个变量，从头开始遍历链表，每经过一个节点，这个变量就自增1。
也就是说，我们需要遍历链表两次，第一次计算出链表中节点的个数，第二次就能获取倒数第K个节点，如下图所示：
- 第1次遍历链表拿到了链表的长度n=6
- 第2次遍历链表获取到了倒数第3个节点处（6-3+1）的值9
遍历一次链表
遍历两次链表来解决这个问题并不是最优解，我们换个思路来考虑下这个问题：准备两个指针。
- 第一个指针从链表的头部开始遍历向前走k-1（3-1=2）步，第二个指针保持不动
- 从第k步开始，第二个指针也开始从链表的头指针开始遍历，两指针同时向前走。
- 由于两个指针的距离始终保持在k-1，当第一个指针到达链表的尾节点时，第二个指针正好指向倒数第k个节点
实现代码
通过上面的分析，我们知道了如何用双指针的思路，只遍历一次链表就能获取链表的倒数第K个节点。接下来，我们来看下代码实现。
首先，我们设计一个名为GetLinkedListNode的类：
- 内部有2个私有变量
- pNext P1指针
- pHead P2指针
- 构造方法接受1个参数：链表头节点
- 对参数进行校验
- 修改两个指针的指向：默认指向链表头节点
export class GetLinkedListNode {
// p1指针
private pNext: ListNode;
// p2指针(与p1指针的距离始终保持在k-1)
private pHead: ListNode;
constructor(listHead: ListNode) {
if (listHead == null) {
throw new Error("链表头节点不能为空");
}
// 初始化两个指针指向
this.pNext = listHead;
this.pHead = listHead;
}
上述代码中，我们用了一个自定义类型ListNode，它描述了一个链表的节点应该包含哪些属性，对此感兴趣的开发者请移步我的另一篇文章：链表与变相链表的实现。
紧接着，实现获取倒数第K个节点函数：
- 接受一个参数K（从1开始），对参数进行有效性校验
- 修改p1指针的指向，将其指向k-1节点，k的范围也要做一下规避处理（其值大于链表总节点数）
- 同步修改p1、p2指针的指向，直至p1指针指向尾节点，p2指针正好指向倒数第K个节点
// 获取倒数第K个节点
getCountdownNode(k: number): ListNode {
if (k <= 0) {
throw new Error("需要获取的倒数节点数必须大于0");
}
// p1指针先走，将其指向链表的k-1位置
for (let i = 0; i < k - 1; i++) {
// k可能出现大于链表总节点的情况，需要进行规避
if (this.pNext.next != null) {
this.pNext = this.pNext.next;
} else {
throw new Error("需要找的节点不存在");
}
}
// 两个指针同时向前走，直至p1指针指向尾节点
while (this.pNext.next) {
this.pNext = this.pNext.next;
if (this.pHead.next) {
this.pHead = this.pHead.next;
}
}
// p2节点正好指向倒数第K个节点
return this.pHead;
}
完整代码请移步👉：GetLinkedListNode.ts
小tips：我们在写代码的时候，一定要尽可能地考虑各种边界情况的处理，最大程度的避免一些错误的发生，提升代码的健壮性。
例如上述代码中所做的处理，最大程度的避免了程序因取不到值而引发的异常报错问题，我们也管这种做法称为防御性编程。
这是一种良好的编程习惯，在编写代码的时候多问问自己“如果不······那么······”这样的问题，提前预见在什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。这样，当异常情况发生时，软件的行为也尽在我们的掌握之中，而不至于出现不可预见的事情。
测试用例
接下来，我们将前言中的例子代入上个章节所实现的函数中，验证下它能否得出正确的结果。
const linkedList = new LinkedList();
linkedList.push(1);
linkedList.push(3);
linkedList.push(5);
linkedList.push(9);
linkedList.push(15);
linkedList.push(21);
const getLinkedListNode = new GetLinkedListNode(linkedList.getHead());
const resultNode = getLinkedListNode.getCountdownNode(3);
console.log(resultNode);
运行结果如下所示，成功的解决了文章前言中所讲的问题。
完整代码请移步👉：GetLinkedListNode-test.ts
注意：上述代码中用到的LinkedList是自定义的一个类，它实现了链表这个数据结构，对其原理感兴趣的开发者请移步我的另一篇文章👉：链表与变相链表的实现。
示例代码
本文所列举的代码，其完整版请移步👇：
写在最后
至此，文章就分享完毕了。
我是神奇的程序员，一位前端开发工程师。
如果你对我感兴趣，请移步我的个人网站，进一步了解。
- 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
- 本文首发于神奇的程序员公众号，未经许可禁止转载💌
评论区