有什么简单的办法检查单链表里是否有环？

mhello

如给定:
typedef struct node {
    char ch;
    struct node *next;
}node_t;

int isCircle( node_t *head);

以这两个条件如何确定单链表里有环存在？

chinaljj

int isCircle( node_t *head)
{
        node_t *pTmpNode;
       
        pTmpNode = head;
       
        while (pTmpNode != head)
        {
                pTmpNode = pTmpNode->next;
                if (pTmpNode == NULL)
                {
                        return false;
                }
        }
        return true;
}

这样应该可以

anhongkui

楼上的不对， 楼主请查找以前的帖子

mhello

问题是这个环可能是由结尾指针指向前边的任意元素，不一定指回头节点？
如：
head-->##-->##-->##-->##-->##--
                        ^                                 |
                         |                                 |
                          ---------------------------
（画得难看，见笑！）
可能我没说清楚，
正常的单链表一般应该是head->##->........->##->NULL，
假如出现异常操作，使得尾指针不是指向NULL，而是指向前面某个元素（不一定指回头节点），
这时假如需要一个接口去判断这个单链表是否是正常链表，这个接口用什么办法（或算法）实现！

福瑞哈哥

1. int isCircle( node_t *head)
   
2. {
   
3.         node_t *q,* p = head;
   
4.         while (p) {
   
5.                 q = p->next;
   
6.                 while (q) {
   
7.                         if (p == q) return 1;
   
8.                         q = q->next;
   
9.                 }
   
10.                 p = p->next;
    
11.         }
    
12.         return 0;
    
13. }

复制代码

怎麼也得兩個循環吧？

chinaljj

So sorry！ I'm wrong

mhello

如果有回环，第二个循环是否有死循环的可能？
如：
head->#->#->#->#->#->#->#->
                             ^                    |
                              |                    |
                               -----------------
这种情况可否正常工作？

福瑞哈哥

原帖由 mhello 于 2007-5-21 11:06 发表
如果有回环，第二个循环是否有死循环的可能？
如：
head->#->#->#->#->#->#->#->
                             ^                    |
                              |           ...

shit，入了陷阱！

mhello

各位大侠，有什么方法可以解决这个问题（先不考虑解决方法的效率问题）？

billzhou

这样可以吗

int isCircle(node_t *head)
{
     node_t *  p=&head;
     node_t *  q=&head;
     while(p->next != NULL && q->next->next!= NULL)
     {
          p=p->next;
          q=q->next->next;

           if(p->ch ==  q->ch)
          return 1;

     }

      return 0;
}



}