剑指Offer(十四):链表中倒数第k个结点

2017年12月1日11:08:19 8 6,989 °C
摘要

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

剑指Offer(十四):链表中倒数第k个结点

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动;从第k步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第k个结点。

效果示意图,以链表总共6个结点,求倒数第3个结点为例:

剑指Offer(十四):链表中倒数第k个结点

除此之外,要注意代码的鲁棒性。需要判断传入参数合法性问题。

2、代码

C++:

Python2.7:

方法与C++一致:

用列表,开辟新空间了,不太好。

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:8   其中:访客  6   博主  2

    • avatar mohican 来自天朝的朋友 谷歌浏览器 Windows 10 陕西省西安市 联通 1

      根据例图,应该是倒数第三个结点

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

          @mohican 已更正,感谢~

        • avatar cgzjdx 来自天朝的朋友 Safari浏览器 Mac OS X 10_13_6 广东省肇庆市 鹏博士长城宽带 2

          不好意思,想问一个问题。。对于C++,pListHead是表头节点,比如一个单链表值为{1,2,3,4,5},那么表头结点之后顺序链接5个节点,每个节点的val依次为1,2,3,4,5,而不是4个节点吧?
          链表这里我有点糊涂了。。
          python和C++好像不一样?一个单链表值为{1,2,3,4,5},那么python表头节点val为1,之后顺序链接4个节点,每个节点的val依次为2,3,4,5,而不是5个节点?

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 联通

              @cgzjdx 单链表的结构是这样的1->2->3->4->5,需要一个一个访问。不能直接访问4所在节点,需要从头节点往后遍历。
              我没看懂你说的意思。

                • avatar cgzjdx 来自天朝的朋友 Safari浏览器 Mac OS X 10_13_6 广东省肇庆市 鹏博士长城宽带 2

                  @Jack Cui 嗯嗯,不是这个意思。。不过我已经弄清楚了,还是谢谢啦。

                • avatar 一书一世界 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市双城区 联通 2

                  @cgzjdx 问题应该是:链表的表头有不同的写法。
                  (1)比如一个单链表值为{1,2,3,4,5},1最为第一个节点(此情况也称为头节点),用一个头指针指向它。
                  (2)同样比如一个单链表值为{1,2,3,4,5},1最为第一个节点(此情况它不是头节点),但是前面还一个节点做头节点(头节点里面的val,不存储任何信息,或者也可以存储链表长度信息),再用一个头指针指向这个头节点。
                  之前看过《大话数据结构》,里面有介绍过这种问题。

                • avatar Dylan 来自天朝的朋友 谷歌浏览器 Windows 7 广东省汕头市 联通 1

                  你好,这个程序是输出倒数k个节点吧?虽然牛客网可以通过

                  • avatar 一书一世界 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市双城区 联通 2

                    本文方法挺巧妙。正常的思路:
                    (1)找到链表结尾,往回查找k个节点。写程序时逆向查找可能不好理解。
                    (2)找到链表结尾,计算链表长度,根据倒数第k个节点可以计算处正数的节点序数,也可输出(需要遍历两次链表)(3)再优化就是本文方法,遍历一次即可。学到了。