牛客題霸 判斷鏈表中是否有環 C++題解/答案

題目描述

判斷給定的鏈表中是否有環
擴展：
你能給出空間復雜度的解法么？

題解：

在這介紹一個簡便的方法：快慢指針
就是：一個指針走兩步，一個指針走一步
快慢指針中，因為每一次移動后，快指針都會比慢指針多走一個節點，所以他們之間在進入環狀鏈表后，不論相隔多少個節點，慢指針總會被快指針趕上并且重合，此時就可以判斷必定有環。
如果快指針到達NULL，說明鏈表以NULL為結尾，沒有環
為什么要這樣？
如果兩個指針只走一步，那就有可能完美錯開，無法相遇，所以要造成速度差，使得能相遇
除了能找環，還可以用來找環入口，這里就不細講了

代碼：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:bool hasCycle(ListNode *head) {ListNode *l1=head;ListNode *l2=head;while((l1!=NULL)&&(l1->next!=NULL)){l2=l2->next;l1=l1->next->next;if(l2==l1)return 1;}return 0;} };

總結

以上是生活随笔為你收集整理的牛客题霸 判断链表中是否有环 C++题解/答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。