解法一:①首先判断是否有环,若无环,则快指针或其下一指针指向空;若有环,则从快慢指针相遇的位置继续出发,直到再次相遇,遍历次数即为环长len。②两指针从头结点重新开始,让其中一指针先出发len步,而后另一指针再出发,相遇节点即为环起点。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(head == NULL || head->next == nullptr) return nullptr; ListNode* fast = head; ListNode*slow = head; while(fast != nullptr && fast->next != nullptr){ fast = fast->next->next; slow = slow->next; if(fast == slow) break; } if(fast == nullptr || fast->next == nullptr) return nullptr; //快慢重新出发,再次相遇时slow所走步数为环长len fast = fast->next->next; slow = slow->next; int len = 1; while(fast != slow){ fast = fast->next->next; slow = slow->next; ++ len; } //二指针回头节点,快指针先走环长len fast = head; slow = head; for(int i = 0; i < len; i ++ ){ fast = fast->next; } while(fast != slow) { fast = fast->next; slow = slow->next; } return fast; } };
解法二:优化的版本。x表示链表头到环起点距离,首次判环相遇点必然距环起点x。另其中一指针从头节点重开,同步同速启动直到相遇即可。
这里有点绕。
详细解释:假定链表起点到入环的第一个节点A的长度为a【未知】,到快慢指针相遇的节点B的长度为(a + b)【这个长度是已知的】。现在我们想知道a的值,注意到快指针p2始终是慢指针p走过长度的2倍,所以慢指针p从B继续走(a + b)又能回到B点,如果只走a个长度就能回到节点A。(假设环内剩余长度为c,则快指针走过的长度为: 2(a+b) = a + b + c + b 所以c=a)
注意一个容易忽略的点,当环非常小而链表非常长时存在快指针在环中遍历不止一次的情况,这样的话上面的a和b存在对环长取余的情况,不过不影响结果。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(head==nullptr || head->next == nullptr) return nullptr; ListNode* fast = head; ListNode* slow = head; while(fast != NULL && fast->next != nullptr){ fast = fast->next->next; slow = slow->next; if(fast == slow) break; } if(fast == nullptr || fast->next == nullptr) return nullptr; fast = head; while(fast != slow){ //slow在环内距起点x+cnt*环长,fast在链表头也距环起点x,同步,相遇。 fast = fast->next; slow = slow->next; } return fast; } };
标签:II,head,slow,142,nullptr,fast,next,链表,ListNode From: https://www.cnblogs.com/luxiayuai/p/17294637.html