题目描述

输入一个链表，输出该链表中倒数第k个结点。

思路

快慢指针思想：设置两个指针，一个快指针，一个慢指针，快指针先走k步，然后快慢指针一起走，直到快指针为空，则慢指针指向的结点即为所求
注意：

• 考虑链表为空，k<=0的情况
• 考虑k超过了链表长度的情况
  （这里我一开始是在循环里加入了一个条件，k=0停止或者快指针走到了空，之后再判断如果快指针为空就返回空，但是有个问题：如果k就等于链表长度的话，这个时候结束的时候快指针也走到了空，但是并不能返回空）
  所以再后来判断的时候不能以快指针为空作为判断k是否超过链表长度的指标，可以以结束时k是否大于0，如果大于0的话证明k是超过链表长度的

代码

错误代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* pFast=pListHead;
        ListNode* pSlow=pListHead;
        if(pListHead==NULL||k<=0)
            return NULL;
        while(k&&pFast!=NULL)
        {
            pFast=pFast->next;
            k--;
        }
        if(pFast!=NULL)  //错误，这里不能用快指针是否为空进行判断，因为如果k就等于链表长度呢？
            return NULL;
        while(pFast!=NULL)
        {
            pFast=pFast->next;
            pSlow=pSlow->next;
        }
        return pSlow;
    }
};

改正代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* pFast=pListHead;
        ListNode* pSlow=pListHead;
        if(pListHead==NULL||k<=0)
            return NULL;
        while(k&&pFast!=NULL)
        {
            pFast=pFast->next;
            k--;
        }
        if(k>0)
            return NULL;
        while(pFast!=NULL)
        {
            pFast=pFast->next;
            pSlow=pSlow->next;
        }
        return pSlow;
    }
};