Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
Follow up: Can you solve it without using extra space?
分析：
当fast与slow相遇时，slow肯定没有遍历完链表，而fast已经在环内循环了n圈(1≤n)。假设slow走了s步，则fast走了2s步（fast步数还等于s加上在环上多转的n圈），设环长为r，则：
2s = s + nr
s = nr
设整个链表长L，环入口点与相遇点距离为a，起点到环入口点的距离为x，则
x + a = nr = (n – 1)r + r = (n - 1)r + L - x
x = (n-1)r + (L – x – a)
L – x – a为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于n-1圈内环+相遇点到环入口点，于是我们可以从head开始另设一个指针slow2，两个慢指针每次前进一步，它俩一定会在环入口点相遇。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode *slow2 = head;
while (slow2 != slow) {
slow2 = slow2->next;
slow = slow->next;
}
return slow2;
}
}
return nullptr;
}
};
时间复杂度o(n),空间复杂度o(1)