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.

Solution

If we know the length of the LinkedList cycle, we can find the start of the cycle through the following steps:

  1. Take two pointers. Let’s call them pointer1 and pointer2.
  2. Initialize both pointers to point to the start of the LinkedList.
  3. We can find the length of the LinkedList cycle using the approach discussed in LinkedList Cycle. Let’s assume that the length of the cycle is ‘K’ nodes.
  4. Move ``pointer2`

.....

.....

.....

Like the course? Get enrolled and start learning!
A

anya.dipalma

· 3 years ago

"As pointer2 is ‘K’ nodes ahead of pointer1, which means, pointer2 must have completed one loop in the cycle when both pointers meet. Their meeting point will be the start of the cycle."

But WHY must their meeting point be the start of cycle? I get that pointer2 is k nodes ahead of pointer1 and that when both pointers meet, pointer2 will b k nodes in the cycle but why does that mean it'll be the start of cycle?

P

Paolo Tormon

· 4 years ago

Easier Python solution

Image

Show 1 reply
K

k

· 3 years ago

3 methods. I Liked 2nd.

While iterating over Nodes, modify every nodes and point them towards temporary variable. If there is loop, you will come back to the Node that is pointing towards temporary variable. That's the Node you are finding! https://www.geeksforgeeks.org/find-first-node-of-loop-in-a-linked-list/

Show 1 reply
adi berkowitz

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
C

CaptainKidd

· 4 years ago

Frankly i'm not 100% sure how this example builds on any previous experience. I guess it's sort of related in that you know how to detect a cycle by this point and can iterate until that's done but the logical jump between that and the Floyd's Tortoise and Hare algorithm seems extreme.

Show 1 reply
M

Matteo

· 3 years ago

The task states "Given the head of a Singly LinkedList that contains a cycle" but one of the test cases fails with my code with a NoneType exception when executing "fast = ".

It seems that or is None but if the list indeed has a cycle in it, then every node would have to have a next node or am I missing something?

I see two possible scenarios:

a) There are test cases where the input list does not contain a cycle.

  • Do others feel that the phrasing of the task is misleading as well?
  • What should the return value be in that case, since there is no beginning of a cycle if there is no cycle?

b) All test cases contain a cycle

  • How can ever be None if there is a cycle?

Note:

  1. I can't add the code directly here because if I save it without using the code block it loses the li
Show 1 reply
S

sharmilasiram

· 2 years ago


#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next

class Solution:
  def findCycleStart(self, head):
    #TODO Write your code here
    if head == None or head.next == None:
      return None
    slow, fast = head, head
    while fast != None and fast.next != None:
      slow = slow.next
      fast = fast.next.next
      if slow == fast:
        slow = head 
        while slow != fast:
          slow = slow.next
          fast = fast.next
        return slow
    return None

I feel like if you don't refine this code, this course is not even worth the money I am paying

Show 1 reply
A

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
ron

ron

· a year ago

does anyone know the name of the algorithm or provide an intuation for the correctness of the algorithm? mainly, the critical part of once a cycle was found and slow = fast, than if we reset slow to the head and .next them simultanasly until they met than they will meet in the start of the cycle necessarly?

U

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