Question

题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

链表结点定义如下：

为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是我们从链表结点的定义可以看出本题中的链表是单向链表，单向链表的结点只有从前往后的指针而没有从后往前的指针，因此这种思路行不通。

既然不能从尾结点开始遍历这个链表，我们还是把思路回到头结点上来。假设整个链表有n个结点，那么倒数第k个结点就是从头结点开始的第n－k＋1个结点。如果我们能够得到链表中结点的个数n，那我们只要从头结点开始往后走n－k＋1步就可以了。如何得到结点数n？这个不难，只需要从头开始遍历链表，每经过一个结点，计数器加1就行了。

也就是说我们需要遍历链表两次，第一次统计出链表中结点的个数，第二次就能找到倒数第k个结点。但是当我们把这个思路解释给面试官之后，他会告诉我们他期待的解法只需要遍历链表一次。

为了实现只遍历链表一次就能找到倒数第k个结点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k－1，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k－1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

下面以在有6个结点的链表中找倒数第3个结点为例分析这个思路的过程。首先用第一个指针从头结点开始向前走两（2=3－1）步到达第3个结点（如图3.5（a）所示）。接着我们把第二个指针初始化指向链表的第一个结点（如图3.5（b）所示）。最后让两个指针同时向前遍历，当第一个指针到达链表的尾结点时，第二个指针指向的刚好就是倒数第3个结点（如图3.5（c）所示）。

图3.5　在有6个结点的链表上找倒数第3个结点的过程

注：（a）第一个指针在链表上走两步。（b）把第二个指针指向链表的头结点。（c）两个指针一同沿着链表向前走。当第一个指针指向链表的尾结点时，第二个指针指向倒数第3个结点。

想清楚这个思路之后，很多人很快就能写出如下的代码：

有不少人在面试之前从网上看到过用两个指针遍历的思路来解这道题，因此听到面试官问这道题，他们心中一阵窃喜，很快就能写出代码。可是几天之后他们等来的不是Offer，却是拒信，于是百思不得其解。其实原因很简单，就是自己写的代码不够鲁棒。以上面的代码为例，面试官可以找出3种办法让这段代码崩溃：

输入的pListHead为空指针。由于代码会试图访问空指针指向的内存，程序崩溃。

输入的以pListHead为头结点的链表的结点总数少于k。由于在for循环中会在链表上向前走k－1步，仍然会由于空指针造成程序崩溃。

输入的参数k为0。由于k是一个无符号整数，那么在for循环中k－1得到的将不是-1，而是4294967295（无符号的0xFFFFFFFF）。因此for循环执行的次数远远超出我们的预计，同样也会造成程序崩溃。

这么简单的代码却存在3个潜在崩溃的风险，我们可以想象当面试官看到这样的代码时会有什么样的心情，最终他给出的是拒信而不是Offer虽是意料之外但也在情理之中。

面试小提示：

面试过程中写代码要特别注意鲁棒性。如果写出的代码存在多处崩溃的风险，那我们很有可能和Offer失之交臂。

针对前面指出的3个问题，我们要分别处理。如果输入的链表头指针为NULL，那么整个链表为空，此时查找倒数第k个结点自然应该返回NULL。如果输入的k是0，也就是试图查找倒数第0个结点，由于我们计数是从1开始的，因此输入0没有实际意义，也可以返回NULL。如果链表的结点数少于k，在for循环中遍历链表可能会出现指向NULL的m_pNext，因此我们在for循环中应该加一个if判断。修改之后的代码如下：

源代码：

本题完整的源代码详见15_KthNodeFromEnd项目。

测试用例：

- 功能测试（第k个结点在链表的中间，第k个结点是链表的头结点，第k个结点是链表的尾结点）。

- 特殊输入测试（链表头结点为NULL指针，链表的结点总数少于k，k等于0）。

本题考点：

- 考查对链表的理解。

- 考查代码的鲁棒性。鲁棒性是解决这道题的关键所在。如果应聘者写出的代码有着多处崩溃的潜在风险，那么他是很难通过这轮面试的。

相关题目：

- 求链表的中间结点。如果链表中结点总数为奇数，返回中间结点；如果结点总数是偶数，返回中间两个结点的任意一个。为了解决这个问题，我们也可以定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。

- 判断一个单向链表是否形成了环形结构。和前面的问题一样，定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（m_pNext指向NULL）都没有追上第一个指针，那么链表就不是环形链表。

举一反三：

当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。