# Share my O(n) time complexity, constant space method based on Linked List Cycle

• The main idea is:

1. Scan the list A and store the last node to be `endA`
2. Let the the next of the `endA` points to the head of the list B
3. Find the loop position of the new list headA
4. Don't forget to keep the original of the list A

The code is below and any comment is welcomed!

``````ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
return nullptr;
}
while (endA->next != nullptr) {
endA = endA->next;
}
// Let the tail of the A points to the head of B

while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
// Keep the original Linked List
endA->next = nullptr;
return slow;
}
}
// Keep the original Linked List
endA->next = nullptr;
return nullptr;
}``````

• It's a smart method! If you are puzzled about it, you can read my analysis~

Assuming that:

``````                   S1 = the distance between headA and the intersection

T = the circle's length                  (S1 + T = all nodes)
``````

And:

``````                   S1 = n*T + delta (int n)
``````

what we know is 'slow''s speed is 1, 'fast''s speed is 2

Before slow == fast ,we need to run
[S1/T]*T + T = (S1 + T - delta) step.

2-Then we set 'fast' = headA .( and set fast's speed to 1)

It means that--now the distance between 'slow' and 'fast' = n*T

3-After another n*T step, slow and fast arrive the intersection!

So, totoaly we move about 2*S1 + T step.
Time complexity is O(n)!

• Thx! I exactly used a lot time on this math work!

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