题目:
输入一个链表,输出该链表中倒数第k个结点。
题目分析:
在这里使用的方法还是快慢指针的方法,不同的是,在这里首先让fast快指针先走k步,然后再让slow和fast同时开始走,即slow=slow->next,fast=fast->next。当fast走到空的时候,slow所在的位置,即为所求的倒数第k个节点。
注意:如果所求的是倒数第0个节点,则直接返回NULL;如果给的k值大于链表的存储的值,则当fast的k步走完之后,fast就为空了,那么也要直接返回NULL。
代码实现:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pListHead ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
if(k == 0)
return NULL;
struct ListNode* slow,*fast;
slow = fast = pListHead;
while(k--)
{
if(fast == NULL)
return NULL;
fast = fast->next;
}
while(fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}