[数据结构与算法]掌握链表（四）—— 剑指22.链表中倒数第k个结点

链表中倒数第k个结点

题目描述

题目来源

思路一、
遍历一遍数组求出长度 count
然后再重第一结点往后走count-k个结点就可以找到倒数第k个的结点

struct ListNode* getKthFromEnd(struct ListNode* head, int k){

   struct ListNode* tmp=head;
   int count=0;
   while(tmp)
   {
       count++;
       tmp=tmp->next;
   }
   count=count-k;
   while(count--)
   {
       head=head->next;
   }
   return head;
}

思路一需要遍历两遍链表，第一次统计出链表中结点的个数，第二次就能找到倒数第k个结点。但是
现在要把遍历两次变回一次，该如何做？
为了实现只遍历一遍链表就能找到第k个结点，我们可以定义两个指针，
两个指针分别为fast和slow然后两个指针初始化为指向第一个结点，fast指针先走k步，fast走完k步后，fast和slow在同步走每一步，直到fast为NULL，当fast为NULL时，slow刚好指向倒数第k个结点
。

思路二、

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

特殊情况：
1.head为空指针。由于代码会试图访问空指针指向的内存，从而造成程序崩溃。
2.输入k 为零
3.输入k为负数
在原有的基础上我们进行改进

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    
    if(k==0||head==NULL)
    {
        return NULL;
    }
    if(k<0)
    {
        k=-k;
    }

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