网页模板网站模板wordpress 小程序

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

链表中倒数第k个结点_牛客网 (nowcoder.com)

思路:

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

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

注意：当链表不为空时，这里的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;

完结

链表中倒数第k个节点的分析就到这里啦，若有不足，欢迎评论区指正，下期见！