Leetcode 141 Linked List Cycle and Leetcode 142 Linked List Cycle II

标题链接

https://leetcode.com/problems/linked-list-cycle/
https://leetcode.com/problems/linked-list-cycle-ii/
题意

给定一个环形链表，求找到链表的环的位置，返回一个指针（以Leetcode 142为例）
题解

起首判定是否有环。可以用快慢指针来确定，由于快的谁人指针不停在环中移动，慢的指针每次移动一步，二者一定会相遇，假如能相遇则阐明有环。第二步假设从链表头到环的出发点距离为a，相遇点为c，那么一定满意a+c+kb = 2(a+c)，则满意a+c = kb,也就是说假如一个指针从链表头开始，另一个指针从相遇点开始走，那么两者相遇的点就是环的出发点。

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode(int x) : val(x), next(NULL) {}
7. * };
8. */
9. class Solution {
10. public:
11.     ListNode *detectCycle(ListNode *head) {
12.         bool hasCycle = false;
13.         ListNode *p1 = head;
14.         ListNode *p2 = head;
15.         while (p1 != nullptr && p1->next != nullptr) {
16.             p1 = p1->next->next;
17.             p2 = p2->next;
18.             if(p1 == p2) {
19.                 hasCycle = true;
20.                 break;
21.             }
22.         }
23.         if(hasCycle) {
24.             ListNode *p3 = head;
25.             while( p1 != p3) {
26.                 p1 = p1->next;
27.                 p3 = p3->next;
28.             }
29.             return p1;
30.         }
31.         return nullptr;
32.     }
33. };

复制代码

时间复杂度：                                   O                         (                         n                         )                              O(n)                  O(n) n是链表的长度
空间复杂度：                                   O                         (                         1                         )                              O(1)                  O(1)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。