Find the start of a linked list loop in O(n) Part 2

Hi again

In the previous post, I wrote about how you can do it in O(n²), now we will do it in O(n).

There's a trivial solution using a hashtable but it will require O(n) extra storage, however, we will attempt to solve it without the O(n) extra storage.

Let's start thinking about how we can do it for a while.

Imagine for instance that we only have a circle and two pointers running in it. One is called "slow" and is at position "0", the other is called "fast" and moves double the speed of slow and is also at position "0". If we start moving them at their relative speeds, when will they meet? fast will complete a cycle when slow is at the middle of the lap then they will meet again at the start point when fast completes two cycles and slow will have completed only one. Now suppose fast has a head-start of "1" position before they start the race. It will meet slow "1" step before the start point", the same applies if it had a head-start of 2, 3, 4, etc.

Now to generalize, have two pointers "fast" and "slow" with fast moving the double speed of "slow" and is "k" steps ahead of slow. they will meet at "k" steps before the start point.

Back to our problem, if we start moving "fast" and "slow" from the head of the above list and consider the length of the line segment before the start of the loop to be "k". Then "slow" will be at the start of the loop while "fast" will have moved "2k" steps from the head of the list, that is, it will be "k" steps ahead of "slow". If we move both of them until they meet. we know they will meet at "k" steps before the start of the loop.

now we start a new point "slow2" and point it to the head of the list, and move it at the same speed with "slow". They will meet after "k" steps at the start of the loop. and we've got our solution in O(n) !

I will post C code for this later.

Find the start of a linked list loop in O(n) Part 1

As for a second post, I decided that it'll be a technical one. I will start publishing solutions to problems that may sound kinda hard.

I'll start with this problem:

Problem: You have a circular linked. Find the node that is the start of the list in O(n).

Now lets first see how we do it in O(n²). This should be easy, you start with two pointers : ahead and behind, you start with ahead = list_head->next and behind = list_head. At each step, you check if ahead->next == behind, if this is the case, then"behind" is the start of the loop, if not, then set "behind" = "behind->next" till "behind" == "ahead". Then repeat the whole thing for the next element in the list.

This should be something like this

if(head == NULL || head->next == NULL)
   return ERROR



for(ahead = head->next; ahead != NULL; ahead = ahead->next)
   for(behind = head; ; behind = behind->next)
      if(ahead->next == behind)
         return behind as the head of the list;
      else if (behind == ahead)
         break;
      else
         behind = behind->next

return ERROR

That's how we do it in O(n²). In the next part I'll show you how we do it in O(n).
Stay tuned.
      

Back again!

So it's been years since I last posted anything in a blog. This blog is gonna be where I post my thoughts, my ideas, my opinions and any random thing that comes up to my mind.

Some of the posts are going to be technical, reflecting my passion for programming, and some are not. Feel free to pass by anytime, you're more than welcome!

See you soon.