判断一个单链表是否有环及环的链接点

xiaoxiao2021-02-28  4

我的机器学习教程「美团」算法工程师带你入门机器学习  以及 「三分钟系列」数据结构与算法  已经开始更新了,欢迎大家订阅~这篇专栏整合了这几年的算法知识,简单易懂,也将是我实体书的BLOG版。

欢迎大家扫码关注微信公众号「图灵的猫」,除了有更多AI、算法、Python相关文章分享,还有免费的SSR节点和外网学习资料。其他平台(微信/知乎/B站)也是同名「图灵的猫」,不要迷路哦~

 

来看看经典面试题的解决方法:如何求解链表的环相关

 

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 }

  执行结果:

 

转载请注明原文地址: https://www.6miu.com/read-1600007.html

最新回复(0)