题目

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

链表结点定义如下：

struct ListNode{    int m_nValue;    ListNode* m_pNext;};

分析

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

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

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

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

代码

ListNode * FindKthToTail( ListNode *pListHead, unsigned int k ){    ListNode *pAhead = pListHead;    ListNode *pBehind = NULL;    for( unsigned int i=0; i
   
     m_pNext;    }    pBehind = pListHead;    while( pAhead->m_pNext !=NULL )    {        pAhead = pAhead->m_pNext;        pBehind = pBehind->m_pNext;    }    return pBehind;}

以上代码缺陷，3种方法能够让代码崩溃：

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

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

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

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

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

ListNode * FindKthToTail( ListNode *pListHead, unsigned int k ){    if( pListHead == NULL || k==0 )        return NULL;    ListNode *pAhead = pListHead;    ListNode *pBehind = NULL;    for( unsigned int i=0; i
   
    m_pNext !=NULL ) pAhead = pAhead-> m_pNext;        else return NULL;    }    pBehind = pListHead;    while( pAhead->m_pNext !=NULL )    {        pAhead = pAhead->m_pNext;        pBehind = pBehind->m_pNext;    }    return pBehind;}

测试用例&代码

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

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

本题考点

（1）对链表的理解

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

举一反三

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

转载地址：http://pkerj.baihongyu.com/

你可能感兴趣的文章

题目

分析

测试用例&代码

本题考点

相关题目

举一反三