聊聊获取链表中倒数第K个节点

给定一个单向链表的头节点，如何获取该链表中倒数第K个节点(从1开始计数)?本文将带着大家一起解决这个问题，欢迎各位感兴趣的开发者阅读本文。,我们通过一个例子来做进一步的分析：,根据单向链表的定义，我们可知：想要获取它的某个节点，只能从头节点开始顺着其指针往后查找。假设整个链表有n个节点，那么倒数第K个节点就是从头节点开始的第n-K+1个节点。如果我们能够得到节点数n，那么只需要从头节点开始往后走n-k+1步就可以了。想要得到节点数n，就需要定义一个变量，从头开始遍历链表，每经过一个节点，这个变量就自增1。,也就是说，我们需要遍历链表两次，第一次计算出链表中节点的个数，第二次就能获取倒数第K个节点，如下图所示：,遍历两次链表来解决这个问题并不是最优解，我们换个思路来考虑下这个问题：准备两个指针。,通过上面的分析，我们知道了如何用双指针的思路，只遍历一次链表就能获取链表的倒数第K个节点。接下来，我们来看下代码实现。,首先，我们设计一个名为GetLinkedListNode的类：,pNext P1指针；,pHead P2指针。,对参数进行校验；,修改两个指针的指向：默认指向链表头节点。,上述代码中，我们用了一个自定义类型ListNode，它描述了一个链表的节点应该包含哪些属性，对此感兴趣的开发者请移步我的另一篇文章：链表与变相链表的实现。,紧接着，实现获取倒数第K个节点函数：,完整代码请移步：GetLinkedListNode.ts。,小tips：我们在写代码的时候，一定要尽可能地考虑各种边界情况的处理，最大程度的避免一些错误的发生，提升代码的健壮性。,例如上述代码中所做的处理，最大程度的避免了程序因取不到值而引发的异常报错问题，我们也管这种做法称为防御性编程。,这是一种良好的编程习惯，在编写代码的时候多问问自己“如果不······那么······”这样的问题，提前预见在什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。这样，当异常情况发生时，软件的行为也尽在我们的掌握之中，而不至于出现不可预见的事情。,接下来，我们将前言中的例子代入上个章节所实现的函数中，验证下它能否得出正确的结果。,运行结果如下所示，成功的解决了文章前言中所讲的问题。,完整代码请移步：GetLinkedListNode-test.ts。,注意：上述代码中用到的LinkedList是自定义的一个类，它实现了链表这个数据结构。,本文所列举的代码，其完整版请移步：