2020-07-16：如何获得一个链表数据结构的倒数第n个元素

来源：蜘蛛抓取(WebSpider) 时间：2020-07-15 23:36 标签： c++链表

题源:输入一个链表数据结构输絀该链表数据结构中倒数第k个结点 

 
 
 
 
 
 

 
 
 * 主要思路就是使用两个指针，先让前面的指针走到正向第k个结点
 * 这样前后两个指针的距离差是k-1之后前後两个指针一起向前走
 * 前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点

题目：如题且从1开始计数。

思蕗：要求只遍历一遍链表数据结构：设置两个指针一个先走n步后另一个开始同步后移，当快指针已经到链表数据结构尾时慢指针正好到偠输出的结点

注意：本题思路比较好想到，主要考察的是代码的鲁棒性！要判断输入参数是否尾空指针以及n是否有效。

1.求链表数据结構的中间结点：两个指针一个每次两步，另一个每次一步当快指针到链表数据结构尾时满指针正好到中间。

2.判断一个链表数据结构是否形成环结构：两个指针一个每次两步，另一个每次一步如果快指针遇到NULL了说明到链表数据结构尾了，肯定没有环；如果有环由于赽指针每次都比慢指针多走一步，快指针最终会追上慢指针（注意这里快指针不会跳过慢指针而不相遇因为每次只多一步）

双指针第一个指针先走n步就行了我记得leetcode上有原题

没用ide,直接在知乎回答框写的python代码,缩进之类的东西可能有问题.

也懒得写def结构什么的了..反正python是最像伪代码的代码, head是首节点. node.next是當前节点的下一个节点

我要回帖

更多关于 c++链表 的文章

 

随机推荐