链表若干

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 判断两个链表是否相交

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

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

比较判断是不是相等 即可

评论