# Linked List Cycle II LeetCode Solution

Difficulty Level Medium
Goldmann SachsViews 28

## Problem Statement

Linked List Cycle II LeetCode Solution – Given the `head` of a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that the tail’s `next` pointer is connected to (0-indexed). It is `-1` if there is no cycle. (Note that `pos` is not passed as a parameter.)

We are not allowed to modify the linked list. ```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.```

## Explanation • `slow` moves 1 step at a time, `fast` moves 2 steps at a time.
• when `slow` and `fast` meet each other, they must be on the cycle
• `x` denotes the length of the linked list before starting the circle
• `y` denotes the distance from the start of the cycle to where `slow` and `fast` met
• `C` denotes the length of the cycle
• when they meet, slow traveled `(x + y)` steps while `fast` traveled `2 * (x + y)` steps, and the extra distance `(x + y)` must be a multiple of the circle length `C`
• note that `x``y``C` are all lengths or the number of steps needed to move.
• `head``slow``fast` are pointers.
• `head` moves `x` steps and arrives at the start of the cycle.
• so we have `x + y = N * C`, let `slow` continue to travel from `y` and after `x` more steps, `slow` will return to the start of the cycle.
• At the same time, according to the definition of x, `head` will also reach the start of the cycle after moving `x` steps.
• so if `head` and `slow` start to move at the same time, they will meet at the start of the cycle, that is the answer.

## Code

### Java Code for

```public class Solution {
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
if (fast == null || fast.next == null) return null;
slow = slow.next;
}
}
}```

### C++ Code for

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

### Python Code for

```class Solution(object):
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow == fast: break
else: return None  # if not (fast and fast.next): return None

## Complexity Analysis for Linked List Cycle II LeetCode Solution

### Time Complexity

O(N) since slow ptr moves to every node.

### Space Complexity

O(1) as we are using two constant iterators for the linked list (slow and fast)

Translate »