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

ArXoR

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

算法 ...

方法是对的, 问题有点点

z应该是p1从A到在B和p2相遇所走过的路程, 才能用那个方程

emacsnw

原帖由 ArXoR 于 2007-2-5 22:38 发表


方法是对的, 问题有点点

z应该是p1从A到在B和p2相遇所走过的路程, 才能用那个方程

p1应该是可以保证没有走完这个环的。

gaosen2463

不能保证吧
如果环特别小呢

gaosen2463

是我想错了
p1是不能走完哪个环

ArXoR

原帖由 emacsnw 于 2/6/07 16:30 发表


p1应该是可以保证没有走完这个环的。

是可以证明z<=y, 但是叙述上应该严谨... ^_^

sdbook

算出循环链的长度，总长度－循环链长度。

tuzhiwei123

访问的接点做个标记，如果发现在访问后面的节点出现标记，就知道从什么地方循环了

dixin01

许多人犯了一个严重的错误，在不知道链表的确切个数的情况下，
是无法进行循环或递归的操作的，这样去求逆转链表或摘取节点，
会因为无法确定循环的结束条件，从而陷入死循环！

以下是我的解答：

struct node* find_cycleNode(struct node *list_x)
{
     struct node *p0, *p1;
     if (list_x==list_x->next)
        return(list_x);
     p1=list_x->next;
     while (1)  {
        for(p0=list_x; p0!=p1; p0=p0->next)
           if (p0==p1->next)
              return(p0);
        p1=p1->next;
     }
}

算法的时间复杂度：O(n^2),  空间复杂度：O(1)

[ 本帖最后由 dixin01 于 2007-4-28 00:11 编辑 ]

emacsnw

原帖由 dixin01 于 2007-4-27 06:28 发表
许多人犯了一个严重的错误，在不知道链表的确切个数的情况下，
是无法进行循环或递归的操作的，这样去求逆转链表或摘取节点，
会因为无法确定循环的结束条件，从而陷入死循环！

以下是我的解答：

struct  ...

两个步进不一样(1和2)的指针相等了就中止，怎么会死循环。

dixin01

原帖由 emacsnw 于 2007-4-28 02:24 发表

两个步进不一样(1和2)的指针相等了就中止，怎么会死循环。

你的算法是正确的，比我的效率高，时间复杂度为O(n)，我说的是其他人的。