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

  • 2
  • 894 °C
  • A+
所属分类:剑指Offer
摘要

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

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

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

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

2、代码

C++:

Python2.7:

方法与C++一致:

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

Jack Cui

发表评论

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

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

    • avatar mohican 1

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