Home » Problem Solving » How to find if a LinkedList has a loop and where the loop is

How to find if a LinkedList has a loop and where the loop is

I think the first time I got asked this question was when I was applying for a summer job after my second year. I am assuming you know what a (singly) LinkedList is by now and you are fairly familiar with its implementation and usage.

Well the first thing that you should think of as always, is understanding the question properly. What does a loop entitle? It means that at the very end, the last node does not point to a null pointer as the next node, but instead it points to a previous node, so you keep looping through a number of nodes.

First try at finding if a LinkedList has a loop.

Well the usual bad way you might think of solving this would be to keep an array and add to it as you go through the LinkedList. Before adding a new node to the array, check if it is already contained. If it is we found the loop. Seems straight forward. Well let’s make a small analysis of this ugly algorithm:

  • Time complexity – For each element in the LinkedList check if it is contained in the array – O(n2)
  • Space complexity – Keep an array of all elements in the LinekdList – O(n)

As we can see this is looking pretty bad. I am sure we can optimize this a lot more. Remember from our Find pairs equal to a sum problem that whenever we see a O(n2) time complexity in arrays we can always try to improve our performance in a two ways:

Second try at finding if a LinkedList has a loop.

First off try to keep the array sorted. This way we will only have to do a Binary Search whenever we check for an item in the list. This will significantly reduce our time complexity:

  • Time complexity – For each element in the LinkedList check if in sorted array and insert. – O(nlog(n))
  • Space complexity – Keep an array of all elements in the LinekdList – O(n)

As you can see we reduced our runtime to O(nlog(n))! Good we have made some improvement but we can do more. The second way we can usually optimize array algorithms with is by putting the elements into a hash table! So let’s think about this.

Third try at finding if a LinkedList has a loop.

Instead of using an array, use a hash table. For every element in the list check if the element is in the hash table. If it is we know we have a loop starting at this exact element! Otherwise we just add it to the list. The time complexity will again improve… or will it?

  • Time complexity – For each element in the LinkedList check if in hash table and insert. – O(n)…?
  • Space complexity – Keep a hash table of all elements in the LinekdList – O(n)

There’s a few problems with this way however. Although on an average case scenario our Hash Table will do the lookup for an element in O(1), we cannot guarantee that the same will happen on the worst-case scenario. Remember that we do not know the size of our list or even the elements prior to creating the list. This is an argument that I see less and less people doing these days butbut we cannot make sure that the numbers of collisions stay below a certain threshold. Hence we cannot say with confidence that the above algorithm will run at O(n) time. For more info check Hash Table Performance

We have exhausted our usual ways of dealing with array problems. But let us think about other “properties” about the problem at hand. There is a loop. How else can we detect a loop?

Fourth and final try at finding if a LinkedList has a loop.

We can keep 2 pointers starting at the beginning of the list. We will call them ONE_STEP and TWO_STEP. As the names can tell, ONE_STEP will go forward one step in the list to the next node and TWO_STEP will go forward two steps in the list. If TWO_STEP ever finds a null pointer then we know the LinkedList has an exit point and hence we have no loop! Otherwise if TWO_STEP meets ONE_STEP we understand that ONE_STEP has been lapped and hence the LinkedList must have a loop.

This is all great but however there is a problem. Although we are guaranteed to find whether we have a loop in the list or not, it is a bit ambiguous to know where the loop starts. Well let’s do a bit of logical/mathematical analysis. Let’s name the place the loop starts as K and the loop size with L. We can infer:

  • When ONE_STEP enters the loop it has done K steps, TWO_STEP has done 2K steps.
  • Therefore TWO_STEP is K steps ahead and needs L – K steps to catch up to ONE_STEP.
  • TWO_STEP catches up at the rate of 1 step / move. Hence they will meet L – K moves after.
  • Summing up, when TWO_STEP catches up, ONE_STEP will have done L – K steps and will be indeed at K steps before the loop starts.

Good! With this in mind we can compile the following algorithm:

  1. Create 2 pointers called ONE_STEP and TWO_STEP and move them forward with 1 and 2 steps appropriately in the list
  2. If TWO_STEP reached a null, we have no loop.
  3. If TWO_STEP points to the same node as ONE_STEP, then we have a loop and we are at K steps from the beginning of the loop
  4. Move TWO_STEP to the beginning of the list and make it move forward with one step.
  5. Moving at the same speed ONE_STEP and TWO_STEP will collide exactly after doing K steps each and hence at the beginning of the loop

Sounds amazing :D. How about we do some performance analysis:

  • Time complexity – Go through the LinkedList with two pointers – O(n)
  • (Auxiliary) Space complexity – Keep a few pointers – O(1)

One thing to note is that when we talk about Space Complexity, we talk about Auxiliary Space Complexity used in the method as we still need to store the List itself somewhere, which will take O(n). Great, so why don’t we get into some coding ;D.

   /**
    * Find and return the index where the loop begins in fooBarHeadNode,
    * If we have no loop, return -1.
    */
   public static int findBeginningOfLoop(LinkedListNode fooBarHeadNode)
   {
      LinkedListNode ONE_STEP = fooBarHeadNode;
      LinkedListNode TWO_STEP = fooBarHeadNode;

      do
      {
         if (TWO_STEP == null || TWO_STEP.next == null)
         {
            return -1;
         }
         
         ONE_STEP = ONE_STEP.next;
         TWO_STEP = TWO_STEP.next.next;
      }
      while (ONE_STEP != TWO_STEP);

      int loopStartIndex = 0;
      TWO_STEP = fooBarHeadNode;
      
      while (ONE_STEP != TWO_STEP)
      {
         ONE_STEP = ONE_STEP.next;
         TWO_STEP = TWO_STEP.next;
         ++loopStartIndex;
      }
      
      return loopStartIndex;
   }

Note how I did a do-while loop to skip extra initializing of the pointers or extra checks for null :).
Well at this point you must be feeling great about yourself, since you (and I), both know how to solve this tricky problem and will definitely ace it in any interview to come up!
Hope you guys enjoyed it… and I’ll see you guys next time ;D.

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media :)

Latest posts by Ajk (see all)

  • John Doe

    The second loop might never end. Try it with 1 -> 2 -> 3 -> 4 ->> 2 (e.g. node 4’s next is node 2).

    • http://www.ajkp.ca Ajk_P

      Interesting: Let’s see.

      First loop:
      ONE_STEP | TWO_STEP
      1 | 1
      2 | 3
      3 | 2
      4 | 4

      Restart TWO_STEP

      ONE_STEP | TWO_STEP | loopIndex
      4 | 1 | 0
      2 | 2 | 1

      Return 1 – correct solution.

      I fail to see the never ending loop….

      • tec5c

        Wouldn’t the first loop go like this….?

        First loop:
        ONE_STEP | TWO_STEP
        1 | 1
        2 | 3
        3 | 1
        4 | 3
        1 | 1

        Edit: Nevermind I misread the original post.

  • quadquintic

    I think step 4 is a bit misleading or a typo. It says “Move TWO_STEP to the beginning of the loop…” I’m fairly sure you actually meant “Move TWO_STEP to the beginning of the list…”

    • http://www.AjkP.ca Ajk

      Good catch! If we knew where the beginning of the loop was we would be done :P

    • http://www.ajkp.ca Ajk_P

      Good catch! Edited.

      If we knew where the beginning of the loop was we would be done

  • Jan-Paul Bultmann

    L – K only for K < L, so IMHO it should be L – (K % L) :)

    • http://www.ajkp.ca Ajk_P

      Very true, wanted to point that out but thought it would be easier to think of it that way.

      The algorithm and code should still work perfectly :)

    • http://www.AjkP.ca Ajk

      Very true, wanted to point that out but thought it would be easier to think of it that way.

      The algorithm and code should still work perfectly :)

  • Mike Zito

    Confusing, I though TWO_STEP would catch up at a rate of 2 steps/move?

    • http://www.FitCoding.com/ Ajk_P

      At the last aglorithm you will note:

      > Move TWO_STEP to the beginning of the list and make it move forward with one step.

      I guess to make it less confusing we could name it QuickStepper or something :)

%d bloggers like this: