每日一题（链表中倒数第k个节点）-Toy模板网

这篇具有很好参考价值的文章主要介绍了每日一题（链表中倒数第k个节点）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

每日一题（链表中倒数第k个节点）

链表中倒数第k个结点_牛客网 (nowcoder.com)
每日一题（链表中倒数第k个节点）,数据结构与算法,链表,数据结构,c语言,开发语言

思路:

如下图所示：此题仍然定义两个指针，fast指针和slow指针，假设链表的长度是5，k是3，那么倒数第3个节点就是值为3的节点。那么我们可以先让fast指针向后走k次，也就是3次。slow指针仍然指向头节点。

每日一题（链表中倒数第k个节点）,数据结构与算法,链表,数据结构,c语言,开发语言

当fast向后走3步之后，如下图所示，此时再让slow指针和fast指针一起向后走，直到fast指针的值为空指针时，此时的slow指针就是倒数第k个指针。

每日一题（链表中倒数第k个节点）,数据结构与算法,链表,数据结构,c语言,开发语言

注意：当链表不为空时，这里的fast指针最后的值一定会为空指针，与链表的节点个数的奇偶性无关。因为当fast先走k步之后，紧接着它就是一步一步的向后走。最后一定会为空指针。

当k的值大于链表的节点个数时，fast指针一定会提前成为空指针，此时直接返回空即可。

代码实现：

struct ListNode* fast = pListHead;
struct ListNode* slow = pListHead;
while(k--)
{

    //链表没有k步长
    if(!fast)
    {
        return NULL;
    }
    fast = fast->next;
}

while(fast)
{
    fast = fast->next;
    slow = slow->next;
}
    return slow;