题目描述
输入一个链表，输出该链表中倒数第k个结点。
示例1
输入

1,{1,2,3,4,5}

返回值

{5}

思路1：暴力查找

直接遍历链表，算出链表长度n，然后倒数第k个，就是输出链表正数第n-k个
注意:以下几种情况直接返回NULL

链表为NULL或者k<=0
k值大于链表长度

代码

typedef struct ListNode Node;
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
    //判断链表非空
    if(pListHead==NULL || k <=0)
    {
        return NULL;
    }
    
    //定义一个计数器用来技术链表长度
    int count =0;
    //遍历链表
    Node * cur = pListHead;
    while(cur)
    {
        cur=cur->next;    //cur指针右移
        ++count;    //计数器+1
    }
    
    //判断k是否大于链表长度
    if(count<k)
    {
        return NULL;
    }
    //新的头节点
    Node * NewHead = pListHead;
    for(int i=0;i<count-k;i++)
    {
        NewHead=NewHead->next;
    }
    
    return NewHead;
    
 }

思路2：快慢指针

设定两个快慢指针，快指针比慢指针先走k步，这样当快指针走到最后一个节点时，慢指针刚好时倒数第k个节点

代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    //设一个快慢指针，快指针比慢指针快n步
    if(pListHead==NULL || k<=0)
    {
        return NULL;
    }
    Node * fast =pListHead;
    
    
    //快指针先走k步
   
    while(k--)
    {
        if(fast==NULL)
            return NULL;
        fast=fast->next;
    }
    
    //慢指针开始走
    Node * slow =pListHead;
    while(fast!=NULL)
    {
        slow=slow->next;
        fast=fast->next;
    }
    
    return slow;
    
}