求有环单链表中的环长、环起点、链表长分析

你猜 阅读:325 2020-10-19 15:34:55 评论:0

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*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 = 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 *ringMeetNode){ 
 56     int RingLength=0; 
 57     LinkNode *fast = ringMeetNode; 
 58     LinkNode *slow = ringMeetNode; 
 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 *ringMeetNode){ 
 71     int lenA=0; 
 72     LinkNode *fast = list; 
 73     LinkNode *slow = ringMeetNode; 
 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 ///如果有环, 释放空空间时需要注意.  
 86 LinkNode* RingStart(Linklist list, int lenA){ 
 87     if (!list || lenA <= 0){ 
 88         return NULL; 
 89     } 
 90  
 91     int i = 0; 
 92     LinkNode* tmp = list; 
 93     for ( ; i < lenA; ++i){ 
 94         if (tmp != NULL){ 
 95             tmp = tmp->next; 
 96         } 
 97     } 
 98  
 99     return (i == lenA)? tmp : NULL; 
100 } 
101  
102 ///释放空间 
103 int freeMalloc(Linklist list, LinkNode* ringstart){ 
104     bool is_ringstart_free = false; //环起始点只能被释放空间一次 
105     LinkNode *nextnode = NULL; 
106  
107     while(list != NULL){ 
108         nextnode = list->next; 
109         if (list == ringstart){ //如果是环起始点 
110             if (is_ringstart_free) 
111                 break;  //如果第二次遇到环起始点addr, 表示已经释放完成 
112             else 
113                 is_ringstart_free = true;   //记录已经释放一次 
114         } 
115         free(list); 
116         list = nextnode; 
117     } 
118  
119     return 0; 
120 } 
121  
122 int main(){ 
123     Linklist list = NULL; 
124     LinkNode *ringMeetNode  = NULL; 
125     LinkNode *ringStartNode = NULL; 
126  
127     int LenA       = 0; 
128     int RingLength = 0; 
129  
130     list = createList(); 
131     ringMeetNode = judgeRing(list); //快慢指针相遇点 
132  
133     if(ringMeetNode == NULL) 
134         printf("No Ring\n"); 
135     else{ 
136         printf("Have Ring\n"); 
137         RingLength = getRingLength(ringMeetNode);   //环长 
138         LenA = getLenA(list,ringMeetNode); 
139  
140         printf("RingLength:%d\n", RingLength); 
141         printf("LenA:%d\n", LenA); 
142         printf("listLength=%d\n", RingLength+LenA); 
143     } 
144  
145     ringStartNode = RingStart(list, LenA);  //获取环起始点 
146     freeMalloc(list, ringStartNode);    //释放环节点, 有环时需要注意. 采纳5楼建议 
147     return 0; 
148 }
View Code

  执行结果:

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

一个IT知识分享的公众号