正文

链表的几个思考题2010-03-24 22:00:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/edwardguo/50826.html

分享到:

链表若干


1.怎么判断链表中是否有环?
(附:怎么快速检测出一个巨大的链表中的死链?)

2.给你一个单向循环链表,怎么找出这个链表循环部分的第一个节点?

3.链表逆序?

4.一个单向链表,不知道头节点,一个指针指向其中的一个节点,问如何删除这个指针指向的节点?

5.给定一个链表的头指针,在一次遍历中,找出这个链表中的中间节点并返回。

6.查找链表中倒数第k个节点(只允许遍历链表一次)

7.编写实现链表排序的一种算法

8.找两个链表的第一个公共节点

9 判断两个链表是否相交

----------------------------
有几个脑壳瓜子都想破都没想一丁点头绪。。。。看来智力还是颇为有限。。。。。

1.怎么判断链表中是否有环?
(附:怎么快速检测出一个巨大的链表中的死链?)
两个指针
一个步长为1,一个步长为2,同时移动。判断其是否相等。
如果数据量巨大的话,http://topic.csdn.net/t/20040906/09/3343269.html

2.给你一个单向循环链表,怎么找出这个链表循环部分的第一个节点?
跟第一个略有不同。第一个只是判断是否有环,而这个是要找出第一个节点。
标记法不错。hash也可以,貌似

3.链表逆序?

4.一个单向链表,不知道头节点,一个指针指向其中的一个节点,问如何删除这个指针指向的节点?
把next节点的key区域复制到本节点,然后删除next节点

5.给定一个链表的头指针,在一次遍历中,找出这个链表中的中间节点并返回。
和1类似

6.查找链表中倒数第k个节点
两个指针,保持距离k

7.编写实现链表排序的一种算法
感觉,插入排序最直接。快排也行,要复杂些,貌似。

8.找两个链表的第一个公共节点
如果有公共节点,那么该节点后面的节点全部都是两链表公共部分。

9 判断两个链表是否相交

如果相交 从相交处开始 到最后一个节点必定重复

所以可以先遍历第一链表到最后个节点 然后再遍历第二个链表取得最后个节点

比较判断是不是相等 即可

阅读(2825) | 评论(1)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册