大家看看这道题～～

阿Q

看到这里人气不怎么样～～发道题让大家看看吧～～

也许大家看过～也许大家觉得简单。。。。嘿嘿～～～

一个单向链表，环的形式如下图；


请设计一个算法实现判断一个链表里是否有环.
要求:
时间复杂度O(n);
空间复杂度O(1);
不能改变链表结构。
大家看看吧，说出算法就行～，注意条件哦～。

Amigo.

.................不懂

天涯海角

目前还做不出来！不知道哪位高手肯指教一下！

smallpig

呼～～～～复杂～～～～偶还没学到～～～

阿Q

应该大二第二学期就教数据结构了～～

钥匙

哪里有图

阿Q

好像链接失效了......我重新传上吧～～～

[ Last edited by 阿Q on 2004-3-12 at 03:13 PM ]

轻轻

为每个结点设一个路过值（初始均为零），路过每次加1，人头结点试图遍历一次，如遇当前结点路过值为1则发现环，退出，如无则最后为空，退出！不知对不对，我对时问复杂度，晕~~~~！

阿Q

空间复杂度O(1);

楼上这样做空间复杂度为O(N).......

钥匙

/*
判断一个单向链表是否有环。
返回值。－1：输入参数不合法；0：无环；1：有环
*/
int islist_loop(list *head)
{
        int flag;
        list *lptr1,lptr2,lptr3;
       
        if(head==NULL)
                return -1;
        if(head==head->next)
                return 1;
       
        lptr1=head->next;
        lptr2=head;
        head->next=NULL;
        while(lptr1!=NULL){
                lptr3=lptr1->next;
                lptr1->next=lptr2;
                lptr2=lptr1;
                lptr1=lptr3;
        }
       
        if(lptr2==head)
                flag=1;
        else
                flag=0;
       
        lptr1=lptr2->next;
        lptr2->next=NULL;
        while(lptr1!=NULL){
                lptr3=lptr1->next;
                lptr1->next=lptr2;
                lptr2=lptr1;
                lptr1=lptr3;
        }
       
        return flag;
}

算法主要是让链表反向，然后判断lptr2的值，当有环时，lptr2指向链头，无环时指向链尾。判断完成后，再次让链表反向，成为原来的链表。还要注意设置开始反向的位置的next位NULL，这样可以结束反向过程。

[ Last edited by 钥匙 on 2004-3-13 at 06:33 PM ]

robby

对于楼上的算法，有待研究中，

总觉哪里出了点问题。

如果无环时，
   while(lptr1!=NULL){
                lptr3=lptr1->next;
                lptr1->next=lptr2;
                lptr2=lptr1;
                lptr1=lptr3;
        }
当执行到尾结点时，lptr1->next不是指向空了吗？？

钥匙

当执行到尾结点时，lptr1->next不是指向空了吗？？
以前是空，但是现在。
lptr1->next=lptr2（尾的前驱）
lptr2现在指向尾。
算法可能微妙一些。但是符合要求

阿Q

int islist_loop(list *head)
{
        int flag;
        list *lptr1,lptr2,lptr3;
        
        if(head==NULL)
                return -1;
        if(head==head->next)
                return 1;
        
        lptr1=head->next;
        lptr2=head;
        head->next=NULL;    //为何?
        while(lptr1!=NULL){
                lptr3=lptr1->next;
                lptr1->next=lptr2;   //不明......??
                lptr2=lptr1;
                lptr1=lptr3;
        }
        
        if(lptr2==head)
                flag=1;
        else
                flag=0;
        
        lptr1=lptr2->next;     //此段代码对flag的值毫无影响,有何用?
        lptr2->next=NULL;
        while(lptr1!=NULL){
                lptr3=lptr1->next;
                lptr1->next=lptr2;
                lptr2=lptr1;
                lptr1=lptr3;
        }
        
        return flag;
}

你说反向?单向链表如何反向?注意不能改变链表结构......

你的过程....我好像看不懂的样子......能简单说下算法吗?细节不用考虑那么多......

钥匙

head->next=NULL;    //为何?
可保证 while结束
lptr3=lptr1->next;
                lptr1->next=lptr2;   //不明......??
                lptr2=lptr1;
                lptr1=lptr3;
反向
  lptr1=lptr2->next;     //此段代码对flag的值毫无影响,有何用?
        lptr2->next=NULL;
        while(lptr1!=NULL){
                lptr3=lptr1->next;
                lptr1->next=lptr2;
                lptr2=lptr1;
                lptr1=lptr3;
        }
再次反向，使得链表结构不变

你可以画一个链表，然后用我的算法试试哦。

[ Last edited by 钥匙 on 2004-3-17 at 06:06 PM ]

钥匙

“你说反向?单向链表如何反向?注意不能改变链表结构......”


单向链表当然可以反向了。

“你的过程....我好像看不懂的样子......能简单说下算法吗?细节不用考虑那么多......”

算法主要是让链表反向，然后判断lptr2的值，当有环时，lptr2指向链头，无环时指向链尾。判断完成后，再次让链表反向，成为原来的链表。还要注意设置开始反向的位置的next位NULL，这样可以结束反向过程。