本文共 1499 字，大约阅读时间需要 4 分钟。

1. 思路

​ 拿到这题，首先最能够想到的是：要想得到倒数第k个节点，但是我只有一个头指针，所以我只能先从头到尾遍历一遍，看看总节点的个数（假设为n），然后再从头遍历（n-k）次即可。这样的话，你总共需要遍历两次，时间上有开销！不过，这也不失为一种解决方案啊！先想出来一个再说，然后跟面试官沟通交流，寻找更优方案。

/* 节点定义为：struct ListNode{	int value;	ListNode* next;};   */ListNode* FindKthNodeToTail(ListNode* pHead, int k){	if(pHead == nullptr || k <= 0)        return nullptr;             // 输入参数有效性判断    ListNode* NodeToTail = pHead;    ListNode* NodeToIter = pHead;    int NumofNode = 1;    while(NodeToTail){    // 总共有多少个节点        NodeToTail = NodeToTail -> next;        NumofNode++;    }    if(k > NumofNode)      // k的取值不能比节点总数还要大        return nullptr;    for(int j = 0; j < NumofNode - k; j++){        NodeToIter = NodeToIter -> next;    }    return NodeToIter;}

​ 面试的时候，如果你这么回答的话，可爱的面试官可能会说：你这样要从头遍历两次哦，我期待你一次就可以搞定！面对面试官这样有礼貌的要求，我们是肯定要满足的是吧😈，哈哈哈。于是，你想到了 快慢指针，没错，用双指针来做！思路是这样的：先让快指针先走 (k - 1)步，然后慢指针才出发。这样的话，快指针与慢指针就保持着 (k - 1)次的循环。直到快指针走到尾节点，那么，慢指针刚好在倒数第k个节点处！太厉害了🍎

代码实现如下：

ListNode* FindKthNodeToTail(ListNode* pHead, int k){	if(pHead == nullptr || k <= 0)        return nullptr;             // 输入参数有效性判断    ListNode* FastPtr = pHead;    ListNode* SlowPtr = pHead;    while(k){        if(!FastPtr)  return nullptr;     // 判断k是否大于节点总数，跟上面的一个步骤是一样的！        NodeToTail = NodeToTail -> next;        k--;        }                    // 循环结束，当k == 0了，那就说明快指针已经走了 k - 1步了。    }    while(FastPtr){        FastPtr = FastPtr -> next;        SlowPtr = SlowPtr -> next;    }    return SlowPtr;}

2. 总结

​ 先考虑出最简单的思路及其实现，然后跟面试官表达自己的想法，交流中再去寻找更优的方案。此题主要是考察双指针的知识。

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