算法-获取链表中倒数第k个结点

题目： 输入一个链表，输出该链表中的倒数第k个结点。比如链表中的值为1，2，3，4，5，6。倒数第三个结点为值为4的结点。链表定义如下：

struct ListNode
{
  int value;
  ListNode *next;
};

解题思路： 这个问题相对来说还是挺好理解的，要找到倒数第k个结点，最直接的思路肯定是倒着数k个结点不就好了，但是问题是链表不能从尾结点开始遍历，只能从头结点开始。 那么倒数第k个的问题基于必须要转化成正数第n-k+1个，其中n是整个链表的长度，那么问题就可以这样解决： （1）先遍历一遍链表，得到链表的长度n； （2）再从头遍历链表，遍历到n-k+1个就是要找到的倒数第k个结点。 但是这种方法必须要遍历两次，那么有没有遍历一次就得到正确结果的方法呢？ 可以通过定义两个指针，第一个指针p1先走k-1步后第二个指针p2再开始走，到k步时两个指针同步走，那么当p1到底链表的结尾时，p2正好走到了第k个结点。

这里写图片描述

此时这种方法牺牲了空间复杂度（两个指针），换来了时间复杂度的降低，这也是设计算法时比较常用的方式—“用空间换时间”。

代码实现：

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 < k - 1; ++ i)
    {
        if(pAhead->next != NULL)
            pAhead = pAhead->next;
        else
        {
            return NULL;
        }
    }
    pBehind = pListHead;
    while(pAhead->next != NULL)
    {
        pAhead = pAhead->next;
        pBehind = pBehind->next;
    }
    return pBehind;
}

上述代码具有较好的鲁棒性： （1）如何输入的 *pListHead 为空，程序返回null而不会异常。 （2）如果输入链表 *pListHead长度小于k个，程序返回null而不会异常。（一个小于k个长度的链表显然没有倒数第k个结点） （3）如果输入的k=0，代码不会异常，而是返回null。