题解 | #链表中倒数最后k个结点#

链表中倒数最后k个结点：最直观的想法是，快慢指针，在没有使用头结点的情况下，快指针使用倒数第一个作为标准，慢指针使用倒数第k个作为标准，快慢指针相差k-1，所以快指针先走k-1步，如果还没走完就已经为空指针，则表示链表长度小于k，并返回空节点nullptr，反之快慢指针一起走，当快指针到达最后一个结点时，返回慢指针，其即为链表中倒数最后k个结点。注意，之所以选择最后一个结点作为快指针的标准，是因为考虑链表长度正好等于k这种特殊情况，慢指针本身起始就指向第一个结点，倒数第链表长度个结点时其是不用走的。

ListNode* FindKthToTail(ListNode* pHead, int k) 
{
    ListNode *p=pHead; //快指针
    ListNode *q=pHead; //慢指针
    while(p&&(--k)) //首先走k-1步 倒数第一个和倒数第k个相差k-1
    {
       p=p->next;
    }
    if(!p) //链表长度小于k
       return nullptr;
    while(p->next) //一起走
    {
       p=p->next;
       q=q->next;
    }
    return q;
}

idea：在使用头结点的情况下，快指针使用倒数第一个的下一个空指针作为标准，慢指针使用倒数第k个作为标准，快慢指针相差k个，所以快指针先走k步，如果还没走完就已经为空指针，则表示链表长度小于k，并返回空节点nullptr，反之快慢指针一起走，当快指针到达最后一个结点的下一个结点时，返回慢指针，其即为链表中倒数最后k个结点。注意，区分使用头结点和不使用头结点的区别。

ListNode* FindKthToTail(ListNode* pHead, int k) 
{
   ListNode *fast=new ListNode(-1),*slow=new ListNode(-1);
   fast->next=pHead; //快指针
   slow->next=pHead; //慢指针
   while(fast&&(k--)) //首先走k步 链表尾部和倒数第k个相差k
   {
      fast=fast->next;
   }
   if(!fast) //链表长度小于k
      return nullptr;
   while(fast) //一起走
   {
      fast=fast->next;
      slow=slow->next;
   }
   return slow;
}