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

Edengundam

原帖由 skipjack 于 2007-2-6 09:50 发表


哦～，我是想用O(n/8)强调空间复杂度为O(0)（可能就是你们常说的O(1)吧，没系统学习过算法，不会专业表达，但我感觉这题也不需要什么算法），gcc结构体4字节对齐时剩下的空间，以及结构体成员变量只要能挤出1 ...

给算法看看吧
你如何管理引用计数??你利用mark的办法吧??
你如何遍历一个可能有环的循环链表, 这样的遍历开销...

O(n/8)就是O(n)意思是: 复杂度和实例规模成线性关系.

skipjack

原帖由 Edengundam 于 2007-2-6 10:08 发表



给算法看看吧
你如何管理引用计数??你利用mark的办法吧??
你如何遍历一个可能有环的循环链表, 这样的遍历开销...

O(n/就是O(n)意思是: 复杂度和实例规模成线性关系.

夸张点～，这题有点像周易里的“悬魂梯”。中国自古推崇易数，早在西周时期，那个最流行推卦演数的时代，统治阶级完全控制掌握着这些秘密，不知比1967年早了多少年。如果找不到“悬魂梯”的结点，就别想从“悬魂梯”上下来。用在古墓里可以防盗哦。

找到你认为需要开销的空间：
1)一个结构体的大小如果是30字节，则在gcc优化的时候一定会扩展为32字节，4字节对齐可以提高访问速度。这两个字节不用白不用，为什么要浪费？当然这个结构体本身就是4字节对齐的，那我还有下面的方式2
2)如果链表中的结构体想在SMP中使用，就必须含有count、use、ref、flag等成员变量用于并行计算，我们大可以使用flag中的某一bit，用于mark。如果你的程序只用在UP环境下，并且不并行....那你自己想办法吧。

算法很简单，每从一个next遍历到下一个结点时，把结点内的mark位由0置为1，当你遍历到8结点返回3结点时，3结点的mark位为1,说明这个3号点是个交点。大步、小步好像需要遍历二次链表，我只需要遍历一次就ok了。

另外test_bit()、clear_bit()、set_bit()，这类函数用汇编很好实现的，效率很高。

Edengundam

原帖由 skipjack 于 2007-2-6 10:36 发表


夸张点～，这题有点像周易里的“悬魂梯”。中国自古推崇易数，早在西周时期，那个最流行推卦演数的时代，统治阶级完全控制掌握着这些秘密，不知比1967年早了多少年。如果找不到“悬魂梯”的结点，就别想从“ ...

首先我们不能假设有空闲bit. 因为总有时候结构体是刚好对齐的.
其次, 如果你每次都需要设置一次, 那么你检查完需要一次清0吧??

Finding a Loop in a Singly Linked List 讨论过这个算法.

1. 
   
2. The problem with this solution is ensuring that "bit" is marked as zero for all
   
3. the nodes before you start. If the linked list has a loop, it isn't possible to
   
4. iterate over each node to set "1" to "0" as an initial value for each node.
   
5. 
   
6. Even if you are able to solve the initial value problem, each node in a linked
   
7. list may not have a field to use for this purpose. Requiring such a field in
   
8. each node would mean that this is not a generic solution. As we will see
   
9. later, this field in not needed for a perfectly correct and efficient solution
   
10. anyway.
    
11. 
    

复制代码

[ 本帖最后由 Edengundam 于 2007-2-6 10:48 编辑 ]

1jjk

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

算法 ...

1. 带环链：1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   10
   
2. 步长2：1   3   5   7   9   11  13  15  10  12   14   16   11        13   15   10   12   14   16   11   13   15   10   12   14   16   11   13   15   10   12   14   16   11   13   15   10   12   14   16   11   13   15   10   12   14   16   11   13   15   10   12   14   16   11    13   15   10
   
3. 步长1：1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   10   11   12   13   14   15   16   10   11   12   13   14   15   16   10   11   12   13   14   15   16   10   11   12   13   14   15   16   10   11   12   13   14   15   16   10   11   12   13    14   15   16  

复制代码

是这样的吗？
在15相遇

skipjack

[quote]原帖由 Edengundam 于 2007-2-6 10:46 发表



首先我们不能假设有空闲bit. 因为总有时候结构体是刚好对齐的.
其次, 如果你每次都需要设置一次, 那么你检查完需要一次清0吧??

Finding a Loop in a Singly Linked List 讨论过这个算法.

1. 
   
2. The ... [/quote]
   
3. 
   
4. [code]
   
5. 你说的清0是为了第二次遍历吧。
   
6. 第一次遍历的时候我以bit为1说明为mark状态
   
7. 第二次遍历的时候我以bit为0说明为mark状态
   
8. mark就是一个二值的翻板，并且当开始遍历的时候我知道翻板的当前状态。
   
9. 
   
10. 至于你说的没有bit用于mark，这就是我一开始说的空间复杂度为O(n/8)的原因，如果有80000个结点，我需要10000个字节来mark。
    

复制代码

Edengundam

原帖由 skipjack 于 2007-2-6 11:04 发表


[code]
你说的清0是为了第二次遍历吧。
第一次遍历的时候我以bit为1说明为mark状态
第二次遍历的时候我以bit为0说明为mark状态
mark就是一个二值的翻板，并且当开始遍历的时候我知道翻板的当前状态。

...

多出来的可以完全不用. 如果对于刚好对其的结构体. 这样开销在某些时候太大了.
这时候浪费就是一个对其长度.
这是非通用解

Edengundam

再PS: 那篇文章应该是有些语境, 而非是一个完整的环境. 使用追赶法可以对现存的各种单链直接进行遍历. 二不需要对原始环境进行任何修改. 这里mark一定要从实践的起步开始全盘设计好. 不过讨论算法总是在一堆算法中找"最优解".

skipjack

原帖由 Edengundam 于 2007-2-6 11:19 发表
再PS: 那篇文章应该是有些语境, 而非是一个完整的环境. 使用追赶法可以对现存的各种单链直接进行遍历. 二不需要对原始环境进行任何修改. 这里mark一定要从实践的起步开始全盘设计好. 不过讨论算法总是在一堆算法中 ...

你说的追赶法最具通用性
我的mark法最具效率

对于复杂和大型的结构体，没有空闲位并且自身还是4字节对齐的情况太少了。
并且当我mark过一个结点后，如果在list_add（）函数中加一个判断，禁止mark后的结点加入链表，从本质上还可以避免这种回环的产生。

具体问题具体分析吧，对于面式的环境，我的回答最具杀伤效果。

BTW：从你的回复中也找到了我想法中的不足，谢谢。

Edengundam

原帖由 skipjack 于 2007-2-6 11:39 发表


你说的追赶法最具通用性
我的mark法最具效率

对于复杂和大型的结构体，没有空闲位并且自身还是4字节对齐的情况太少了。
并且当我mark过一个结点后，如果在list_add（）函数中加一个判断，禁止mark后的结 ...

我也长了很多见识, 把自己没有考虑的也顺便问了你. 呵呵, 同谢~~~

lovefreex

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


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

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

我觉得这个方法可行的(如果可以访问链表中的数据),可以依次取链表的前一部分(保存该部分的最后一个结点的指针域并将其赋值为null),判断后面一部分是否有循环,如果没有则指针域为空的那个结点为循环点,如果有,则恢复那个空指针,截取下一个结点