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

你猜阅读：792 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*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 = 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.作者投稿可能会经我们编辑修改或补充。