[牛客]链表中倒数第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;之前,原因可自行分析

---

结语：

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

希望以上内容对大家有所帮助👀，如有不足望指出🙏**

前路漫漫！努力变强💪💪 吧！！

---