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

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

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

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

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

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

2、代码

C++:

Python2.7:

方法与C++一致:

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

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

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

目前评论:6   其中:访客  4   博主  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 Dylan 来自天朝的朋友 谷歌浏览器 Windows 7 广东省汕头市 联通 0

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