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

yeleven86

刚发现是07年的帖子，汗哪

folklore

回复 5# cjaizss


    如果空间为O N，你还用时间为O N^2，真是费CPU，有ON的空间的话，一次就可能找到，准确的话是：O N+1次。

xdyang1986

发现大家都好牛啊，学习中……

cjaizss

回复  cjaizss


    如果空间为O N，你还用时间为O N^2，真是费CPU，有ON的空间的话，一次就可能找到， ...
folklore 发表于 2010-10-18 01:57

   ……
O(f(n))是讲无穷大级别的，O(n)和O(n+1)没有区别

folklore

回复 114# cjaizss


    O N==O N+1，没错，笔误，我想说是N+1次～～

看题目可知，NULL为一特殊的值。
则可以这样：将各个链表的ID（或其它可标志值）设为0～N-1，将N个指针（所以事实上只要ON个指针空间p[N]，而不是ON的空间）设为NULL。
遍历一次，过程中将p[ID]设为指向当前结点的指针。这样，如果当前的指针为NULL，将无LOOP，不然就是第一次冲突的就是首结点。

action08

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

用大步小步法，小步步幅为 1， 大步步幅为 2，经过 i 步后重 ...
win_hate 发表于 2007-02-05 19:43

    这个性能太差，可以牺牲空间改进的