21ic电子技术开发论坛 › 单片机与嵌入式系统 › 嵌入式操作系统论坛 › 请教各位一个单向链表的访问方法
返回列表 发新帖我要提问

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

[复制链接]
3257|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

粉丝
快速回复 在线客服 返回列表 返回顶部