JZ14 链表中倒数第k个结点

题目描述

输入一个链表,输出该链表中倒数第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;
    }
};
全部评论

相关推荐

05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务