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

win_hate

设非循环部分有 a 个点， 循环部分有 b 个点

用大步小步法，小步步幅为 1， 大步步幅为 2，经过 i 步后重合。从重合点出发，搜索自身并记数，可以得到 b.

令 q = [(i-1)/b]

用两个指针，一个从 qb +1 点出发，一个从重合点出发，步幅为1，直到重合，经过的步数就是 r. 而 a=bq+r.

[ 本帖最后由 win_hate 于 2007-2-5 21:01 编辑 ]

azhoulinux

是否可以这样考虑：
单链表每一个节点其指向下一个节点的指针都是不同的，这道题在于会出现
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循环
2节点与8节点都是指向3节点，引入一个新的栈，存储每个节点指针的值，一旦出现相同的指针值，那么就可以说出现了循环，比如2节点与8节点都是指向3节点.

你们看看行不行？

Edengundam

O(1)复杂度...意思是常量, 不随着实例规模的变化而变化. 一万个指针, 都应该记为O(1)...呵呵


O(n/应该表示为O(n)的复杂度...

zjw12112

构造hash表，我觉得时间复杂度是0(nlog2^n)吧？不好意思，忘了hash的时间复杂度。
想出了一个空间复杂度为0(n),时间复杂度也为0(n)的算法，不知道是否可行，大家看一看。
首先根据链表创建一个逆序的链表。如下：
原始：1->2->3->4->5->6->7->8->(3)
逆序：1->2->3->8->7->6->5->4->(3)
赫赫，接下来就很容易判断了，分别从两个链表头指针开始，找到next指针不一样的那个节点就是最终目标了。

12013396

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

标准答案!!

Edengundam

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

恩...明白这个算法的意思...偶太弱了..这算法1967年就有了...

emacsnw

想了一下，似乎下面的算法可以：O(1)空间，O(n)时间。
两个额外指针p1, p2，开始都指向头S。设需要找到的循环部分第一个结点的位置为A，S到A的距离为x (x可能为0），链表的循环部分长度为y (y > 0)。

算法开始和判断循环的方法一样：令p1每次走一步，p2每次走两步，我们知道，如果链表有环，最后p1和p2一定在环上某个地方B相遇，我们设A-B之间的距离为z (z可能为0)。

很显然，p1走了x+z步，那么p2走了2(x+z)步，由于p1和p2在这么多步后相遇，因此有2(x+z) - (x+z) = K*y (K > 0的整数)，因此我们有x+z = K*y。

假如我们能让p1在B点开始继续往前走x步的话，它一定会走到A，因为z+x是y的倍数。有人会说，费话如果知道x的话，我只要让p2从起点S开始往前走x步，不就也能走到A吗？其实解法就是这么简单，让p1在刚刚相遇的地方B继续一次走一步，而p2从起点S开始一次走一步，那么它们第一次相遇的地方一定是A，并且正好经过了x步（当然你不需要计数）。

这就是算法。还是比如下面的例子：0->1->2->3->4->5->6->7->8->(3)
刚开始p1, p2都在0，p1一次走一步，p2一次走两步，它们最终会在结点6相遇。这时候让p1继续从6开始往前走，而p2从0开始也一次往前走1步，那么我么就会发现它们会相遇在3，返回这个地址就是所需要的解。

lishengxu

老兄你的算法不对阿2(x+z) - (x+z) = K*y
这等式有问题阿!!!!
因该是2(x+n*z)-(x+m*z) = k*y

[ 本帖最后由 lishengxu 于 2007-2-6 09:26 编辑 ]

emacsnw

原帖由 lishengxu 于 2007-2-5 17:23 发表
老兄你的算法不对阿2(x+z) - (x+z) = K*y
这等式有问题阿!!!!
因该是2(x+n*z)-(x+m*z) = k*y

p2比p1多走了环长的整数倍，有什么问题吗？

skipjack

原帖由 Edengundam 于 2007-2-5 20:32 发表
O(1)复杂度...意思是常量, 不随着实例规模的变化而变化. 一万个指针, 都应该记为O(1)...呵呵


O(n/应该表示为O(n)的复杂度...

哦～，我是想用O(n/强调空间复杂度为O(0)（可能就是你们常说的O(1)吧，没系统学习过算法，不会专业表达，但我感觉这题也不需要什么算法），gcc结构体4字节对齐时剩下的空间，以及结构体成员变量只要能挤出1个bit用于计数，就足够了。比什么大步、小步、二叉、折半，效率高多了。