阿Q 发表于 2004-1-9 00:19

大家看看这道题～～

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

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

一个单向链表，环的形式如下图；
http://photos.gznet.com/photos/1223972/1223972-F926bsiR5f.JPG

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

Amigo. 发表于 2004-1-11 12:55

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

天涯海角 发表于 2004-1-18 02:40

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

smallpig 发表于 2004-1-22 06:35

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

阿Q 发表于 2004-1-27 18:03

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

钥匙 发表于 2004-3-11 18:58

哪里有图

阿Q 发表于 2004-3-12 15:11

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

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

轻轻 发表于 2004-3-12 23:36

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

阿Q 发表于 2004-3-13 15:01

空间复杂度O(1);

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

钥匙 发表于 2004-3-13 18:27

/*
判断一个单向链表是否有环。
返回值。－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 发表于 2004-3-14 10:41

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

总觉哪里出了点问题。

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

钥匙 发表于 2004-3-14 10:51

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

阿Q 发表于 2004-3-17 00:25

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;
}


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

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

钥匙 发表于 2004-3-17 18:04

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 ]

钥匙 发表于 2004-3-17 18:08

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


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

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

算法主要是让链表反向，然后判断lptr2的值，当有环时，lptr2指向链头，无环时指向链尾。判断完成后，再次让链表反向，成为原来的链表。还要注意设置开始反向的位置的next位NULL，这样可以结束反向过程。
页: [1]
查看完整版本: 大家看看这道题～～