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.