Grokking the Coding Interview: Patterns for Coding Questions

0% completed

Solution: Start of LinkedList Cycle

Problem Statement

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.

About the input. The test harness builds the list from two lines. The first line lists the node values in order. The second line is the zero-based index of the node that the last node points back to, so it is the cycle entry. For [1,2,3,4,5,6] and 2, the tail links back to the node holding 3, and 3 is the answer. Every test on this question supplies a real cycle, as the statement promises.

.....

Like the course? Get enrolled and start learning!

Dante Tsang

· 5 months ago

This should be better solution in js

findCycleStart(head) { 
	let slow = head, fast = head; 
	// Phase 1: find meeting point 
	while (fast !== null && fast.next !== null) { 
		slow = slow.next
		fast = fast.next.next
		
		if (fast === slow) { 
			// Phase 2: find cycle start 
			slow = head 
			while (slow !== fast) { 
				slow = slow.next
				fast = fast.next // both move 1 step now! 
			}
			return slow // they meet at cycle start 
		}
	}
	return null // no cycle
}

Show 1 reply

Aydar Nabiev

· 9 months ago

A linked list with a cycle looks like this:

μ (mu) = number of nodes before the cycle starts (distance from head to cycle entry)
λ (lambda) = cycle length

Example shape:

head → ... (μ nodes) ... → [CYCLE ENTRY] → ... → (λ nodes loop back)

Compute cycle length λ.
Put two pointers at head:

p1 = head
p2 = head

Move p2 ahead by λ steps.
Move both p1 and p2 one step at a time. They will meet at the cycle entry.

Why moving ahead by λ makes them meet at cycle start

Key invariant

At all times during step 4:

p2 is exactly λ nodes ahead of p1 along the list.

Because you advanced p2 by λ at the start, and then you move both pointers equally (1 step per iteration), the gap stays constant.

I sugge

Show 1 reply

umesh

· a year ago

Let:

l = distance from head to start of cycle
m = distance from start of cycle to meeting point of fast and slow pointer
k = length of the cycle
This gives, k - m = distance from meeting point to start of cycle

When fast and slow meet inside the cycle:

slow distance = l + m  
fast distance = l + m + n·k (some multiple of the cycle)

Since fast moves twice as fast:

2(l + m) = l + m + n·k → l + m = n·k

From this:

l = n·k - m = (k - m)  (mod k)

This means:

Distance from head to start of cycle and met point to start of the cycle are same.
So, if you start one pointer at head and the other at meeting point,
And move both 1 step at a time, they will cover same distance and meet at the start of the cycle for

Show 1 reply

ron

· 2 years ago

Show 1 reply

Viktor Shevchenko

· 2 years ago


public class Solution {
  public ListNode findCycleStart(ListNode head) {
    var next = head;
    while(next != null && next.Next != null)
    { 
      var previous = next;
      next = next.Next;
      previous.Next = null; 
    }
    return next;
  }
}

Show 2 replies

Tu Huy Nguyen

· 2 years ago

Should add the check if no cycle is found:

  def detectCycle(self, head):
    cycle_length = 0
    slow, fast = head
    while fast and fast.next:
      fast = fast.next.next 
      slow = slow.next
      if slow == fast: 
        cycle_length = self.calculate_cycle_length(slow)
        break
    # HERE: should handle case where no cycle is found.
    if fast is None or fast.next is None:
        return None

    return self.find_start(head, cycle_length)

Show 2 replies

sid-patel

· 2 years ago

class Solution:
  def findCycleStart(self, head):
    slow, fast = head, head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      // when the two pointers meet, rest anyone pointer back to head and then step one at a time
			// until they meet again. the point they meet is the starting of the cycle.
      if slow == fast:
        slow = head
        while slow!=fast:
          slow = slow.next
          fast = fast.next
        return slow
    return None

lejafilip

· 2 years ago

Why we need to use slow/fast pointer approach while we can just store some unique value of each node? In c++ we can use memory address.

It is simply O(n), because we iterate over all list but we have also O(n) memory for HashSet.

Algorithm is simple. We need to iterate and add each pointer to hashSet until we come across already added one. Then return pointed address.

Code:

ListNode *findCycleStart(ListNode *head) {
    std::unordered_set<ListNode*> visitedNodes;    
    ListNode* it = head;

    do
    {
      visitedNodes.insert(it);
      it = it->next;
    }while(!visitedNodes.contains(it));
    
    return it;
}

Show 1 reply

adi berkowitz

· 2 years ago

Here is the solution that is clean and 100% be the official solution

class Solution:
  def findCycleStart(self, head):
    slow, fast = head, head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if fast == slow:
        break
    slow = head
    while slow != fast:
      fast = fast.next
      slow = slow.next
    return slow

Show 1 reply

Adrian Adewunmi

· 2 years ago

Good job on this course, Design Guru. However, LeetCode has published a more concise solution (in java).

// Design Guru Problem Statement: Start of LinkedList Cycle
// LeetCode Question: 142. Linked List Cycle II
public class Problem_3_Start_Of_LinkedList_Cycle {
    class ListNode{
        int val = 0;
        ListNode next;

        public ListNode(int value){
            this.val = value;
        }
    }

    public ListNode findCycleStart(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == head) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;

Show 1 reply

Reading Progress

Vote for new content