本文主要是介绍检查链表是否有环，返回值为bool和从头节点进入环的第一个节点两种情况，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目1（不返回节点）
给定单链表，检查链表是否有环。
代码实现：
bool IsCircle(List plist)
{assert(plist != NULL);if (plist == NULL||plist->next==NULL)return false;Node* p = plist->next;//慢指针,一次走一步Node* q = plist->next->next;//快指针，一次走两步while (q!= NULL&&q->next!=NULL){if (p == q){break;}else{p = p->next;q = q->next->next;}}if (q == NULL || q->next == NULL){return false;}else{return true;}}
题目2（返回节点）
给定单链表（head），如果有环的话请返回从头节点进入环的第一个节点。
思路：
给定慢指针p->next;快指针q->next->next。如图，假设快、慢指针在点3相遇，快指针走过的路径是慢指针的两倍。
慢指针走过的路径长度：m+n
快指针走过的路径长度：m+c*x+n
快指针走过的路径是慢指针的2倍，所以，2*（m+n）=m+c*x+n
由上式得到m=c*x-n=c*x-n+c-c=c*(x-1)+c-n，即m的长度比圆的周长倍数多出c-n的长度，相遇点加上c-n的位置就是进入环的第一个节点。
代码实现：
Node* FirstCircleNode(List plist)
{assert(plist != NULL);if (plist == NULL||plist->next==NULL)return NULL;Node* p = plist->next;//慢指针Node* q = plist->next->next;//快指针for (p, q; q != NULL && q->next != NULL; p = p->next, q = q->next->next){if (p == q)break;}if (q==NULL||q->next==NULL)//没有环{return NULL;}//快慢指针相遇了Node* s = plist;//1while (s != q){s = s->next;q = q->next;}return s;
}int main()
{Node head;InitList(&head);for (int i = 0; i < 10; i++){Insert_tail(&head, i);}Show(&head);Node* p1 = FirstCircleNode(&head);if (p1!=NULL)printf("有环,%d\n",p1->data);elseprintf("无环\n");//Node* q = Search(&head, 3);//链表中的某一个节点（数据域为3）//Node* s = Search(&head, 9);//尾巴节点//s->next = q;//Node* p2 = IsCircle(&head);//if (p2 != NULL)// printf("有环,%d\n", p2->data);//else// printf("无环\n");Node* q = Search(&head, 5);//链表中的某一个节点（数据域为5）Node* s = Search(&head, 9);//尾巴节点s->next = q;Node* p2 = FirstCircleNode(&head);if (p2 != NULL)printf("有环,%d\n", p2->data);elseprintf("无环\n");return 0;
}
这篇关于检查链表是否有环，返回值为bool和从头节点进入环的第一个节点两种情况的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
