educative.io

Isn't there a far more efficient way to find the start of a linked list cycle?

Courses
,
#1

Why are we figuring out the length of the cycle? Can’t you just prove there is a cycle, and then move one pointer back to the start, and then advance both pointers by 1 spot until they meet again? I forget the name of the algorithm, but I’m pretty sure that always works and is easier to understand, and doesn’t require the extra step of determining the length of the cycle

1 Like
#2

yup, that’s the one i recalled. it can be proved mathematically and reasoned about.
assume slow ptr has speed v, and fast ptr has speed 2v (or think about distance)
assume head to beginning of loop is a.
assume loop has distance b.
assume c is where both ptr meet from the beginning of the loop.
by the time when they meet
fast ptr => 2v = a + mb + c
slow ptr => v = a + c
subtract both equations
v = mb (m times the loop with b being the distance)
v = a + c
thus mb = a + c
you don’t know how many times you travelled in the loop, and assuming you don’t know how long b is.
however
you know at c location, you need to travel ‘a’ distance to be at the beginning of the loop again ( you could pass the beginning of loop many times, however by traveling ‘a’ distance you for sure will be a the beginning of the loop)
and you can start with the head, travel ‘a’ distance to goto the beginning of the loop. and that’s the definition of a.

#3

Yes that seems to be the easier solution. It’s called Floyd’s algorithm for cycle detection.

#4

I believe there is a better approach using set. I would use just one pointer visiting every single node. Then I check if pointer.next exist in the set I created. If not then add the pointer value into the set. If the pointer.next exist in the set, that is when I found out the cycle. This would minimize the code written, but I am not sure if my solution applies for all cases.

  const find_cycle_start = function(head){
  let set1 = new Set();
  let start = head;
  while (start !== null && start.next !== null){
    if(set1.has(start.next)){
      return start.next;
    }else{
      set1.add(start);
      start = start.next;
    }
  }
  return start;
};
#5

I like this solution too, but the thing is that the space complexity becomes O(N). With the cycle detection, it is O(1).