链表中倒数第k个结点

链表中倒数第k个结点

http://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a

描述

这是一篇针对初学者的题解。用2种方法解决。
知识点:链表,链表的快慢指针
难度:一星


题解

方法一:普通解法

很显然,求倒数第k个,可以转换成求正数第多少个呢?
看个例子:
![图片说明](https://uploadfiles.nowcoder.com/images/20200412/284295_1586659181233_3FB7A40FAFE34EE9211313F42EACD5D4 "图片标题")
假设有5个节点,序号1表示第1个节点,假设求倒数第K个,那么正数就应该是从头结点开始往后推(n-k)个,n自然代表所有节点的个数(不包含空节点),也可以说n代表指针的个数,为啥这么说呢?因为一个节点后面跟着一个指向下一节点的指针。
这里n=5,所以需要从头结点往后经过n-K = 3个指针。
![图片说明](https://uploadfiles.nowcoder.com/images/20200412/284295_1586659791197_9BA2F66B522AB7AE08799525A7D3EE27 "图片标题")

有了上面的过程,还需要考虑2个细节

  1. k<=0 或者头结点最开始就为空,也就是没有节点
  2. 节点的总个数 < K

代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (!pListHead || k &lt;= 0) return nullptr;
        int n = 0;
        ListNode *cur = pListHead;
        while (cur) {
            cur = cur-&gt;next;
            ++n;
        }
        if (n &lt; k) return nullptr;
        n -= k;
        while (n--) {
            pListHead = pListHead-&gt;next;
        }
        return pListHead;

    }
};

时间复杂度:O(2*n),n为链表的总长度,如果k总是在倒数第一个节点,那么此方法需要遍历链表2次
空间复杂度:O(1)

方法二:严格的O(n)解法,快慢指针

如下图:
![图片说明](https://uploadfiles.nowcoder.com/images/20200412/284295_1586660964310_C8DDCF9578B57797652591CAE5690D6C "图片标题")

我们从图中可以看出,倒数第k个节点与最后的空节点之间有2个指针,此时的2正好就是k,于是我们可以想到可以通过平移来到达最后的状态。
如图:
![图片说明](https://uploadfiles.nowcoder.com/images/20200412/284295_1586661598005_61C7E2391D7ECF5878F3F8FD90B552FC "图片标题")

如果懂了上面的过程,接下来再说说具体编程要怎么写?
![图片说明](https://uploadfiles.nowcoder.com/images/20200412/284295_1586661740629_9B71D46EC6391DE19469F8B223EDA6CA "图片标题")
使用如图的快慢指针,首先让快指针先行k步,然后让快慢指针每次同行一步,直到快指针指向空节点,慢指针就是倒数第K个节点。

代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (!pListHead || k &lt;= 0) return nullptr;
        auto slow = pListHead, fast = pListHead;

        while (k--) {
            if (fast)
                fast = fast-&gt;next;
            else 
                return nullptr; //如果单链表长度 &lt; K,直接返回
        }
        while (fast) {
            slow = slow-&gt;next;
            fast = fast-&gt;next;
        }
        return slow;
    }
};

时间复杂度:O(n),不管如何,都只遍历一次单链表
空间复杂度:O(1)

全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
fRank1e:吓得我不敢去外包了,但是目前也只有外包这一个实习,我还要继续去吗
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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