# Share my O(n) complexity and constant space code. Keep the original list. Any comments.

• The idea is :

1. First, scanning the list using `slow` and `fast` pointers, and using `slowVal`, `fastVal` records the steps two pointers have past. If the list has loop, then `fastVal - slowVal` equals the size of the loop.
2. Then, let `slow` points head, and `fast` points `loopSize` ahead.
3. Let slow and fast points the next until `slow == fast`, here we found the begin of the loop.

Here, we scan the list twice, and use constant space.
The code:

``````ListNode *detectCycle(ListNode *head) {
return NULL;
}
ListNode *slow = head, *fast = slow->next;
long long slowVal = 0, fastVal = slowVal + 1;
while (fast != NULL){
if (slow == fast){
break;
}
slow = slow->next;
fast = fast->next;
++slowVal;
++fastVal;
if (fast != NULL){
fast = fast->next;
++fastVal;
}
}
// No loop
if (fast == NULL){
return NULL;
}
long long loopSize = fastVal - slowVal;
while (loopSize){
fast = fast->next;
--loopSize;
}
while (slow != fast){
slow = slow->next;
fast = fast->next;
}
return fast;
}
``````

• slowVal and fastVal are unnecessary. When fast == slow , they just point loopSize. So the code can be simplified as follows,

``````class Solution {
public:
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return NULL;
}
};``````

• Thanks very much for your advice! That exactly makes the code more concise.

• If the list is 1-2-3-4 and 4 links back to 2, your solution returns 4. Is it correct? I expect it to return 2.

• fastVal - slowVal is not necessary loopsize. It is multiple of loopsize. Consider 1-2-3-4-5, 5 links back to 4.

• I guess that the 1-2-3-4 input is not correct for the case that 4 links back to 2, maybe 1-2-3-4-2? And my method will return 2. Thanks about your advice and I also find the fastVal and slowVal is not necessary:)

• Just a bit more explanation on the math logic behind the above algorithm.

Assume that the distance from the head of the list to the joint point of the ring is `K`. The size of the ring is `RING_SIZE`. (Note: here we assume `RING_SIZE > K`. It is easy to derive the proof for the case where `RING_SIZE < K`). Two pointers: slow and fast; the slow pointer moves one step at a time, and the fast pointer moves two steps at a time.

The algorithm locates the joint point of the ring within a linked list, in O(N) time complexity and constant space complexity, via the following steps.

1. Both pointers start from the head of list. In `K` steps, the slow
pointer reaches the joint point, while the fast pointer is K steps
away from the joint point, since the fast pointer moves two times
faster than the slow one. In other words, we could say that the
fast pointer is `(RING_SIZE - K)` lagging behind the slow pointer, if
the movement continues.

2. To catch up with the slow pointer, it takes `2*(RING_SIZE-K)`
steps for the fast pointer. At the same time, the slow pointer is
`(RING_SIZE-K)` away from the joint point. In other words, both
pointers now, are `(RING_SIZE - (RING_SIZE-K)) = K` steps to the joint
point.

3. Now we could move the slow pointer to the head of the list, and
keep the fast pointer at the first meeting point. Now, if both
pointers move at the same pace, one step at a time, they would meet
again, in `K` steps. And this time, as we can see from the step 2),
they would meet at the joint point.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.