【学習点滴-データ構造-単鎖表】単鎖表にループがあるか否かを判断する

/*
 *     ：     ，         。 
 *     ：
 * 1.initLinkList():           。
 * 2.initLoopList():       。
 * 3.isLoopLink():        。 
 * @author:xiaoq-ohmygirl
 * @time :2012-06-25 
 **/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAXNODE 5

//       
typedef struct linkNode{
    int data;
    linkNode * next;
}linkNode,*linkList;


//                  
int initLinkList(linkList & L,int n){
    L = (linkList)malloc(sizeof(linkNode));
    if(!L){
        return 0;
    }
    scanf("%d",&L->data);
    L->next = NULL;
    linkList p;
    for(int i = n-1;i > 0;i--){
         p = (linkList)malloc(sizeof(linkNode));
         scanf("%d",&p->data);
         p->next = L->next;
         L->next = p;
    }
    return 1;
}


//      k        loop,           。 assert(n>=k) 
int initLoopLink(linkList &L,int n,int k){
    L = (linkList)malloc(sizeof(linkNode));
    if(!L){
        return 0;
    }
    scanf("%d",&L->data);
    L->next = NULL;
    linkList p,node;
    for(int i = n-1;i > 0;i--){
         p = (linkList)malloc(sizeof(linkNode));
         scanf("%d",&p->data);
         p->next = L->next;
         L->next = p;
    }
    node = L; 
    for(int i = 0;i < k;i++){
        node = node->next;            
    }
    p = node;
    while(node->next != NULL){
        node = node->next;    
    }
    node->next = p; 
    return 1; 
} 


//         。     ：       ，                ，     ，     ，         ，       。 
linkList isLoopLink(linkList L){
    linkList first = L,second = L;
    while(first != NULL && first->next != NULL){
          first = first->next->next;
          second = second->next;
          if(first == second){
               return first;             
          }  
    }
    return NULL;     
} 


main(){
    linkList L = NULL,p = NULL;
    initLinkList(L,MAXNODE);
    p = isLoopLink(L);
    printf("%s",p == NULL?"not loop":"loop"); 
    
    initLoopLink(L,MAXNODE,2); 
    p = isLoopLink(L);
    printf("%s",p == NULL?"not loop":"loop");    
    system("pause"); 
    return 0;  
}