1 # include<stdio.h>  2 struct Slist{  3     int size;  4     struct sl* head;  5 };  6 struct sl{  7     int k;  8     struct sl* next;  9 }; 10 typedef struct Slist Sl; 11 typedef struct sl sl; 12 void init(Sl* m,int k){ 13     sl* p = (sl *)malloc(sizeof(sl));     14     p->k = k; 15     p->next = NULL; 16     m->head =p; 17     m->size = 1; 18 } 19  20 sl* add(Sl* m,int key ){ 21     sl* p=(sl *)malloc(sizeof(sl));  22     sl* q = (sl *)malloc(sizeof(sl)); 23     p->k = key; 24     p->next = NULL; 25     q = m->head; 26     while (q->next != NULL) 27         q = q->next; 28     q->next = p; 29     m->size++; 30     return p; 31 } 32  33 void FanZhuan(Sl* m){                            //链表反转 34  35     sl* p = m->head; 36     sl* q =NULL;  37     sl* r =NULL; 38     while (p->next!=NULL){ 39  40         q = p->next; 41         p->next = r; 42         r = p; 43         p = q; 44     } 45     q->next = r; 46     m->head = q; 47 } 48  49 void BianLi(Sl* m){                                 //遍历链表 50  51     sl* a = m->head; 52     printf(" \n"); 53     while (a != NULL){ 54         printf("%d",a->k); 55         a = a->next; 56     } 57 } 58  59 sl* CheckLoop(Sl* m){                                //测试是否有环 60     sl* a = m->head; 61     sl* b = m->head; 62     while (b!=NULL){ 63         a = a->next; 64         if (b->next == NULL) 65             return NULL; 66         if (b->next->next == NULL) 67             return NULL; 68         b = b->next->next; 69         if (a == b) 70             return a; 71     } 72     return NULL; 73 } 74  75 int NloopCheck(Sl* f,Sl* n){            //两者均无环，测相交 76     sl* k1 = f->head; 77     sl* k2 = n->head; 78     while (k1->next!=NULL) 79     { 80         k1 = k1->next; 81     }                                   //取得表k1的最后一个节点 82     while (k2 != NULL){ 83         k2 = k2->next; 84         if (k2 == k1) 85         { 86              return 1; 87         } 88     } 89     return 0; 90 } 91  92 void Check(Sl*t1,Sl*t2){                     //测试是否相交 93  94     sl* Y1 = CheckLoop(t1);                  //先测两个表的每个表是否有环 95     sl* Y2 = CheckLoop(t2); 96 //    if (Y1 != NULL) 97 //        printf("The first have loop!\n"); 98 //    if (Y2 != NULL) 99 //        printf("The second have loop!");                        100 101     int y1 = (Y1 != NULL);102     int y2 = (Y2 != NULL);103     int y = y1 + y2;104     int yes = 0;105     sl* test = NULL;106     switch (y)107     {108     case 0:                                       //均无环109         printf("\n Two have no loop!");110         yes = NloopCheck(t1, t2);111         break;112 113     case 1:                                       //一个有环，一个没有114         printf("\n One Have loop!");115         yes = 0;116         break;117 118     case 2:                                       //两者都有环119         printf("\n Two have loop!");120         test = t2->head;121         while (1)122         {123             if (test == Y2)124             {125                 yes = 1;126                 break;127             }128             test = test->next;129         }130         break;131     default:132         break;133     }134 135     if (yes == 1)136         printf("\n Have intersection!");137     else138         printf("\n Don‘t have intersection!");139 }140 141 void main(){142     Sl* t1 = (Sl*)malloc(sizeof(Sl));                 //创建带环链表t1143     t1->size=0;144     t1->head = NULL;145     init(t1,8);146     add(t1, 3);147     add(t1, 2);148     sl* t1Start=add(t1, 1);                           //loop start!149     add(t1, 0);150     add(t1, 9);151     sl* t2Start=add(t1, 10);152     t2Start->next = t1Start;                           //Add loop!153     154     Sl* t2 = (Sl*)malloc(sizeof(Sl));                 //创建链表t2与t1相交155     t2->size = 0;156     t2->head = NULL;157     init(t2, 8);158     add(t2, 3);159     add(t2, 2);160     sl* w2 = add(t2, 1);161     w2->next = t2Start;162 163 164     Sl* t3 = (Sl*)malloc(sizeof(Sl));                 //创建五环链表t3165     t3->size = 0;166     t3->head = NULL;167     init(t3, 8);168     add(t3, 3);169     add(t3, 2);170     sl* w3= add(t3, 1);171     add(t3,7);172     add(t3,27);173 174     Sl* t4 = (Sl*)malloc(sizeof(Sl));                 //创建链表t4与t3相交175     t4->size = 0;176     t4->head = NULL;177     init(t4, 8);178     add(t4, 3);179     add(t4, 2);180     sl* w4 = add(t4, 1);181     w4->next = w3;182 183     Sl* t5 = (Sl*)malloc(sizeof(Sl));                  //创建链表t5，不与上相交184     t5->size = 0;185     t5->head = NULL;186     init(t5, 8);187     add(t5, 53);188     add(t5, 42);189 printf("\n SingList t1 and t2:");190 Check(t1, t2);191 printf("\n\n SingList t3 and t4:");192 Check(t3, t4);193 printf("\n\n SingList t1 and t3:");194 Check(t3, t1);195 printf("\n\n SingList t3and t5:");196 Check(t5, t3);197     198     199     200     201     system("pause");202 }