带环聊表问题

   今天一哥们突然问怎么判断一个链表时候有环,回答取一个节点然后遍历链表再次找到这个节点就Ok了..突然想起以前那道百度题,判断两个聊表示不是相交那个,链表有环并不是所有的节点都在环上吗...

    貌似又废话了好多^_^。这里判断了链表是不是有环以及环的长度,引申下你可以求在哪里开始出现环之类的了.

  

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUMS 20
#define MAX_VALUES 100

typedef struct list
{
   int num;
   struct list* next;
 }LIST;
 
void init_head(LIST** H)
{
   *H = (LIST*)malloc(sizeof(LIST));
   (*H)->next = NULL;
 }

void printf_list(LIST* H)
{
  LIST* p = H->next;
  int count = 0;
  
  while(p!=NULL)
   {
    if(++count%5 == 0)
     printf("%d\n",p->num);
    else
     printf("%d\t",p->num);
    
     p = p->next;
    }
}

int init_list(LIST* H)
{
   int i = 0;
   int num;
   LIST* p = H;
   LIST* q = NULL;
          
   for(;i<MAX_NUMS;i++)
    {
      num = rand()%MAX_VALUES + 1;
      q = (LIST*)malloc(sizeof(LIST));
      q->num = num;
      p->next = q;
      q->next = NULL;
      p = q;
     }
   
   printf("before loop the list is:\n");
   printf_list(H);
   num = rand()%10+5; //num is between 5-15

   
   q = H;
   for(i=0;i<num;i++)
     q = q->next;
   
   printf("loop at %d\n",q->num);
    
   p->next = q;
  
   return 0;
 }
 
int check_loop(LIST* H)
{
  LIST* p = H->next;
  LIST* q = H->next->next;
  int ret = 0;
  
  while((p!=NULL)&&(q!=NULL))
   {
       if(p==q)
        {
          ret = 1;
          break;
         }
        else
        {
           p = p->next;
           q = q->next->next;
         }
    }
   
   p = p->next;
   while(p != q)
    {
     p = p->next;
     ret++;
     }
     
   return ret;
}
     
int main(int argc, char *argv[])
{
  int ret = 0;
  LIST* H = NULL;
  srand((unsigned)time(NULL));
  init_head(&H);
  init_list(H);
  
  ret = check_loop(H);
  if(ret)
  {
    printf("there is loop\n");
    printf("the loop have total %d nodes\n",ret);
  }
  
  system("PAUSE");    
  return 0;
}