首页 > 代码库 > 求有环单链表中的环长、环起点、链表长
求有环单链表中的环长、环起点、链表长
1.判断单链表是否有环
使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。
就是所谓的追击相遇问题：
2.求有环单链表的环长
在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。
设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：
环长=2*len-len。
3.求有环单链表的环连接点位置
第一次碰撞点Pos到连接点Join的距离=头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。
在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。
第一次相遇时，slow走的长度 S = LenA + x;
第一次相遇时，fast走的长度 2S = LenA + n*R + x;
所以可以知道，LenA + x = n*R; LenA = n*R -x;
4.求有环单链表的链表长
上述2中求出了环的长度；3中求出了连接点的位置，就可以求出头结点到连接点的长度。两者相加就是链表的长度。
编程实现：
下面是代码中的例子：
具体代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 typedef struct node{ 4 int value; 5 struct node *next; 6 }LinkNode,*Linklist; 7 8 /// 创建链表(链表长度，环节点起始位置) 9 Linklist createList(){ 10 Linklist head = NULL; 11 LinkNode *preNode = head; 12 LinkNode *FifthNode = NULL; 13 for(int i=0;i<6;i++){ 14 LinkNode *tt = (LinkNode*)malloc(sizeof(LinkNode)); 15 tt->value =http://www.mamicode.com/ i; 16 tt->next = NULL; 17 if(preNode == NULL){ 18 head = tt; 19 preNode = head; 20 } 21 else{ 22 preNode->next =tt; 23 preNode = tt; 24 } 25 26 if(i == 3) 27 FifthNode = tt; 28 } 29 preNode->next = FifthNode; 30 return head; 31 } 32 33 ///判断链表是否有环 34 LinkNode* judgeRing(Linklist list){ 35 LinkNode *fast = list; 36 LinkNode *slow = list; 37 38 if(list == NULL) 39 return NULL; 40 41 while(true){ 42 if(slow->next != NULL && fast->next != NULL && fast->next->next != NULL){ 43 slow = slow->next; 44 fast = fast->next->next; 45 } 46 else 47 return NULL; 48 49 if(fast == slow) 50 return fast; 51 } 52 } 53 54 ///获取链表环长 55 int getRingLength(LinkNode *meetNode){ 56 int RingLength=0; 57 LinkNode *fast = meetNode; 58 LinkNode *slow = meetNode; 59 for(;;){ 60 fast = fast->next->next; 61 slow = slow->next; 62 RingLength++; 63 if(fast == slow) 64 break; 65 } 66 return RingLength; 67 } 68 69 ///获取链表头到环连接点的长度 70 int getLenA(Linklist list,LinkNode *meetNode){ 71 int lenA=0; 72 LinkNode *fast = list; 73 LinkNode *slow = meetNode; 74 for(;;){ 75 fast = fast->next; 76 slow = slow->next; 77 lenA++; 78 if(fast == slow) 79 break; 80 } 81 return lenA; 82 } 83 84 ///释放空间 85 int freeMalloc(Linklist list){ 86 LinkNode *nextnode = NULL; 87 while(list != NULL){ 88 nextnode = list->next; 89 free(list); 90 list = nextnode; 91 } 92 } 93 94 int main(){ 95 Linklist list = NULL; 96 LinkNode *meetNode = NULL; 97 int RingLength = 0; 98 int LenA = 0; 99 100 list = createList();101 meetNode = judgeRing(list);102 103 if(meetNode == NULL)104 printf("No Ring\n");105 else{106 printf("Have Ring\n");107 RingLength = getRingLength(meetNode);108 LenA = getLenA(list,meetNode);109 110 printf("RingLength:%d\n",RingLength);111 printf("LenA:%d\n",LenA);112 printf("listLength=%d\n",RingLength+LenA);113 114 freeMalloc(list);115 }116 return 0;117 }
执行结果：
本文网址：http://www.cnblogs.com/xudong-bupt/p/3667729.html
参考网址：http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html