剑指OFF|输入一个链表,输出该链表中倒数第k个结点?

今天是元宵节在这祝大家元宵节快乐,我今天第一天写文章数据结构也是学的比较薄弱算法那就更别说,但我相信只要自己可以坚持的学下去一定会得到提高的。

个人观点:工作这么这么久虽然工作上用的算法不多,但却让我感到学好数据结构和算法对于一个程序员事多么的重要,至少你是个有思想的程序员而不是只是复制粘贴的码农,那话不多说看看这道题的解法吧!

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

刚开始看到这道题的时候完全没有一点思路因为我的 算法基础还是比较薄弱的, 但对于一些算法大佬这种题目那是看一下就知道怎么去写了,对于我来说还是有些难度的。

参考剑指off上一些大佬的写法从中能到一些思路,画了一个简单的草图比较丑

这是个人觉得比较好理解的思路拿过来分享一下。

二、解题思路

  • 1.传统的我们可以这么理解,比如在二个一样长的木桥上有两个人站在桥头要求出桥倒数第k步的位置在那? 解:我们可以先让第一个人先走k步,那么剩余的步数就是n-k步,当第一个人走到k步的位置时,第二个人和第一人同时走,当第一个人走完的时候,第二个人停住,停住的地方即为倒数第k步的位置。
  • 此题感觉可以拿来作为一个测试题来发挥自己的想象。
  • 2.正常的思路理解,设链表的长度为N。设置两个指针p1和p2,先让p1移动k个节点,则还有n-k个节点可以移动,此时让p1和p2同时移动,可以知道当p1移动到链表的结尾时,p2移动到n-k个节点处,该位置就是倒数第k个节点。

三、代码实现

public class Solution {

四、总结

这道题还是相对比较简单的从这道题的解题思路类似于数学上的对称,那个利用两个指针对开始的地方走k步即是到过来的k步,但是我们怎么得到呢?

利用两个指针思想还是非常的巧妙的。用第二个指针记录第一个指针从第k个位置走完的位置即第二个指针走完n-k个位置那第二个指针的位置就是倒数第k个位置。从这个思想上我们扩散出许多的题目类型,也可以让自己的思维跳出局限。

觉得文章不错,记得转发分享给更多同学哦~

点赞、转发和辣条会提升颜值哦~

- END -

关注我

每天进步一点点

原文发布于微信公众号 - 技术从心(gh_d845efe513db)

原文发表时间:2019-02-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券