发新帖我要提问
返回列表
打印

请教各位一个单向链表的访问方法

[复制链接]
2164|3
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
sjl2006|  楼主 | 2009-9-17 21:27 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
单向链表, 节点
面试时被问到：一个单向链表，长度不定，要找到倒数第四个节点，有什么方法？
从链表头往后数感觉效率太低了，请问各位，还有其他更高效的办法么？

使用特权

评论回复 赏

相关下载

相关帖子
沙发
踢球老越位| | 2009-9-17 21:45 | 只看该作者
你弄两个指针，第一个指向第一个表，第二个指向第四表，然后就同时数咯，当第二个指针指到最后时，第一个指针指向的就是倒数第四个了，你就不用再往回数了。

使用特权

评论回复 赏
板凳
sjl2006|  楼主 | 2009-9-18 08:21 | 只看该作者
谢谢楼上的解答：）
不过还是有疑问：单向链表是不能往回寻址的，我的想法是在固定的表头节点中保存链表的长度，前向寻址时指针移动长度减4即可，和楼上的方法类似，都是从表头往后数~~但是如果链表很长的话，循环次数就会很多。有没有其他更好的办法呢？

使用特权

评论回复 赏
地板
mohanwei| | 2009-9-18 08:36 | 只看该作者
没有办法，它的特性就决定了。
除非把链表头放到一个指针数组里，数据随意，这样链表操作速度就跟普通数组一个级别了。
但是带来的麻烦是，如果要动态添加，就会带来频繁释放、申请内存的问题……但但是，这个问题也可以通过一开始就申请一块足够大的内存来避免。

使用特权

评论回复 赏
返回列表
发新帖 我要提问
高级模式
B Color Image Link Quote Code 收费 Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

sjl2006

3

主题

189

帖子

1

粉丝