Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
For the similar question, I don't think we need to iterate through the cycle aga...

hj3yoo

Feb 22, 2022

For the similar question, I don't think we need to iterate through the cycle again.

The fast pointer travels twice as fast as the slow pointer, and it has covered the same distance that the slow pointer has covered plus an entire cycle. Mathematically, this means that: 2 * d_slow = d_slow + d_cycle, which simplifies to d_cycle = d_slow.

Therefore, we can keep track of how many nodes the slow pointers travelled until the fast pointer meets it and return that value.

Haven't tested in code, but please correct me if I'm wrong.

2

0

Comments
Comments
A
Angel Morales4 years ago

I thought the same thing and tried it and got the same result.

M
Mikhail Putilov3 years ago

You are right! I was not sure at first, this is my reasoning about it:

u = speed d = distance t = time

general formula: u = d / t

our case: t is the same u_2 - u_1 = 1 // the fast pointer is twice as fast as the slow one

Let's fix the moment 't' when two pointers me...

R
rsinaf 3 years ago

The problem with the formula is that it assumes that fast wont be going through the cycle several times before slow catches up with it.

I think that having d_cycle = d_slow only works if the length of the cycle is at least Ceil(list.length / 2) .

sealess
sealess2 years ago


class Solution:
  def findCycleLength(self, head):
    # Initialize slow and fast pointers to the head of the linked list
    slow, fast = head, head
    count =0 
    # Traverse the linked list using slow and fast pointers
    while fast is not None and...
sealess
sealess2 years ago


class Solution:
  def findCycleLength(self, head):
    # Initialize slow and fast pointers to the head of the linked list
    slow, fast = head, head
    count =0 
    # Traverse the linked list using slow and fast pointers
    while fast is not None and...

On this page