AlgoViz
HomeLinked List

Find the starting point in LL

Medium

Restart one pointer at the head

Problem

Given the head of a singly linked list, the task is to find the starting point of a loop in the linked list if it exists. Return the starting node if a loop exists; otherwise, return null. A loop exists in a linked list if some node in the list can be reached again by continuously following the next pointer. Internally, pos denotes the index (0-based) of the node from where the loop starts. Note that pos is not passed as a parameter.

In simple words

After slow/fast meet, move one pointer to the head; they meet again exactly at the loop's start.

The idea

After the slow and fast pointers meet, move one of them back to the head and advance both one step at a time; they meet again exactly at the cycle's entry. The distance arithmetic of Floyd's algorithm guarantees it.

The trick

  • Phase 1 finds a meeting point, phase 2 finds the entry.
  • In phase 2 both pointers move one step at a time.
  • O(n) time, O(1) space.
slow
fast
3
2
0
-4
⟲

Step 1 of 5. Slow moves one step, fast moves two. In a loop the fast pointer eventually laps the slow one.

1/5
Optimal
timeO(n)spaceO(1)

They meet iff a cycle exists.

1let slow = head, fast = head;2while (fast && fast.next) {3  slow = slow.next;4  fast = fast.next.next;5  if (slow === fast) return true;6}7return false;

Input

list
[3, 2, 0, -4]

Memory

slow
= 0
fast
= 0

Output

cycle
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3 -> 4 -> 5, tail links to index 2
Output:
3
Explanation:
The loop begins at node 3.

Example 2

Input:
list = 1 -> 2, tail links to index 0
Output:
1
Explanation:
The loop starts at the head.

Example 3

Input:
list = 1 -> 2 -> 3, no loop
Output:
-1
Explanation:
No cycle → -1.

Constraints

  • 0 <= number of nodes in the cycle <= 10^5
  • 0 <= ListNode.val <= 10^4
  • pos is -1 or a valid index in the linked list

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.