Leetcode——输出链表倒数第k个节点

题目原型：

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 示例： 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.

思路一： 最简单的方法，对链表进行遍历，唯一的难点就是要知道倒数第n个节点即为正数第n-k个节点，n为链表的长度。

typedef struct ListNode node;
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
   node* cur=pListHead;
   node* count=pListHead;
   if(pListHead==NULL || k<=0)
   {
       return NULL;
   }
   int n=0;
    while(count!=NULL)
    {
        count=count->next;
        n++;
    }
    if(n<k)
    {
        return NULL;
    }
    while(n-k)
    {
        cur=cur->next;
        n--;
    }
    return cur;
}

思路二：双指针

利用的就是快慢指针的思路，首先让第一个指针fast指向第k个节点，此时fast与slow指针的间隔为k，再将两指针同时开始走，当fast指针走到空时，此时slow指针指向的就是倒数第k个节点。

struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
     struct ListNode* fast=head;
     struct ListNode* slow=head;
     while(k)
     {
         fast=fast->next;
         k--;
     }
     while(fast!=NULL)
     {
         slow=slow->next;
         fast=fast->next;
     }
     return slow;
}