链表中倒数第k个节点是[牛客]吗？

本文共计541个文字，预计阅读时间需要3分钟。

牛客链表使用快慢指针法：两种思路：

1.快先向后走k-1次，慢再向后走1次，然后快慢同时向后走，当快走到最后一个节点时，慢正好在倒数第k个位置；

2.快先向后走k次，慢再向后走，直到快到尾节点。

牛客链接

使用快慢指针法:

两种思路:

1.fast先向后走k-1次,slow再向后走1次,然后fast和slow同时向后走,当fast走到最后一个结点时,slow刚好在倒数第k个位置上;

2.fast先向后走k次,slow再向后走1次,然后fast和slow同时向后走,当fast走到最后一个结点的后面时(此时为NULL),slow刚好在倒数第k个位置上;

根据这个思路,我们可以写出初始代码如下:

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast,*slow; fast = slow = pListHead; while(k--)//循环k次 { fast = fast->next;//fast向后走k次 } while(fast)//当fast为空时,slow指向倒数第k个结点 { slow = slow->next;//不为空,同时向后走 fast = fast->next; } return slow; }

需要注意代码中while(k--)是循环k次,而while(--k)是循环k-1次.

这样看,代码似乎没什么问题,但是运行之后报了错:

这时我们需要通过测试用例来进行分析

通过第三个用例,我们可以考虑到链表为空的情况

通过第四个用例,考虑到k多于链表结点数时的情况

进行逻辑分析和修改后的代码如下:

正确代码

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { if(pListHead == NULL)//链表为空 { return NULL; } struct ListNode* fast,*slow; fast = slow = pListHead; while(k--) { if(fast== NULL)//当k>链表结点数时 { return NULL; } fast = fast->next; } while(fast) { slow = slow->next; fast = fast->next; } return slow; }

需要注意的是代码中的if(fast == NULL)语句必须放在fast = fast->next;之前,原因可自行分析

结语：

这里本章内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。

希望以上内容对大家有所帮助