一个关于单向链表的面试题。

emacsnw

我同学最近面试某IT公司的电话面试一个题目，他说当时可能回答的不好，和我讨论了一下。这里来问问大家。

给你一个单向链表的头指针，可能最后不是NULL终止，而是循环链表。题目问你怎么找出这个链表循环部分的第一个节点。比如下面的链表：

1. 
   
2. 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循环
   

复制代码

就应该返回结点3的位置。

当然尽量用少的空间和时间是题目的要求。

cjaizss

两个指针，一个步长为1，一个步长为2，往前进，时间复杂度O(n),空间复杂度O(1)

converse

原帖由 cjaizss 于 2007-2-5 14:17 发表
两个指针，一个步长为1，一个步长为2，往前进，时间复杂度O(n),空间复杂度O(1)

这个题目和原来的判断链表是不是循环链表的问题有一些区别的,原来是要证明链表是不是循环的,现在的是已知某部分是循环的要求找到这个循环的头结点.

我想到的办法是,从头开始一次取出把链表中的结点组成另一个链表,判断这个链表是不是循环的,第一个满足条件的头结点就是了.

比如以上面的测试数据为例:
第一次取出:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)
第二次取出:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)
第三次取出:
2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)

以此类推.

不知道有没有更好的办法,关注.

boxpei

所有节点排序，第一个重复出现的节点就是，抛砖引玉。

cjaizss

原帖由 converse 于 2007-2-5 14:23 发表


这个题目和原来的判断链表是不是循环链表的问题有一些区别的,原来是要证明链表是不是循环的,现在的是已知某部分是循环的要求找到这个循环的头结点.

我想到的办法是,从头开始一次取出把链表中的结点组成另一 ...

恩，刚才没细想，现在想想确实是那么回事情。
空间复杂度O(n),时间复杂度O(n^2)
构造一个长度为O(n)的buffer,折半查找插入排序
无论是空间复杂度，还是时间复杂度，这已经是极限。
级别无法提高，但是或许可以找到同一级别上更快的算法。

Edengundam

原帖由 converse 于 2007-2-5 14:23 发表


这个题目和原来的判断链表是不是循环链表的问题有一些区别的,原来是要证明链表是不是循环的,现在的是已知某部分是循环的要求找到这个循环的头结点.

我想到的办法是,从头开始一次取出把链表中的结点组成另一 ...

和我想得大致一样...但是复杂度O(n^2)

Edengundam

原帖由 boxpei 于 2007-2-5 14:30 发表
所有节点排序，第一个重复出现的节点就是，抛砖引玉。

这个应该是O(nlogn)了...主要开销是对指针地址排序...

这个我说错了...取所有节点地址的开销貌似..

[ 本帖最后由 Edengundam 于 2007-2-5 15:12 编辑 ]

bleem1998

原帖由 cjaizss 于 2007-2-5 14:17 发表
两个指针，一个步长为1，一个步长为2，往前进，时间复杂度O(n),空间复杂度O(1)

我的基于这个算法
首先确认是否存在循环
如果存在循环
那么最后两个指针相会的地方一定是在循环的圈圈里
如果对这个节点不断的做next的话
会出现死循环
OK
这个时候再从链表头头上开始
把每个节点都判断一下是否在那个循环的圈圈里


这个算法不的内存消耗率为0
咩哈哈哈

lishengxu

不太明白converse的算法，希望斑竹给解释一下呗~
你第一次取出了第一个节点，但是你只知道头节点，不知道尾节点和链表的长度啊？
你怎么能判断出什么时候第一次结束啊？
我觉得最好是能够给访问过的节点做上已经访问的标志，这样不就好办了么！

converse

原帖由 lishengxu 于 2007-2-5 14:44 发表
不太明白converse的算法，希望斑竹给解释一下呗~
你第一次取出了第一个节点，但是你只知道头节点，不知道尾节点和链表的长度啊？
你怎么能判断出什么时候第一次结束啊？
我觉得最好是能够给访问过的节点做上已 ...

是啊,不知道哪里结束是个问题,我马虎了.