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

ゝ一世哀愁。 2022-06-11 05:53 179阅读 0赞

**题目：**  
输入一个链表，输出该链表中的倒数第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个结点。  
![这里写图片描述][SouthEast]  
此时这种方法牺牲了空间复杂度（两个指针），换来了时间复杂度的降低，这也是设计算法时比较常用的方式—“用空间换时间”。

**代码实现：**

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。

[SouthEast]: /images/20220611/7b25726d91964f5380f27340da91e203.png