# Samuel Jacob's Weblog

Just another technical blog

## Fix loop in a linked list

Cycle or loop in a linked list with nodes is shown in pictorial representation.

In this picture the number of nodes in the list is and the last node points to node at a position x(which created the cycle). From the picture it is obvious that to fix the loop:

1. Find the last element
2. Correct it to point end(NULL)

In the above steps, step 1(find the last element) is little difficult if total number of nodes in the list is unknown. In this post I will describe a method I discovered to find the last node. I drew couple of pictures to explain the complexity of the problem. The following pictures explains the same loop condition but in different form. It explains why it is hard to find the last node.  The illustration also tells us the following where is total number of nodes in the list is number of nodes before the cycle starts. is number of nodes forming the cycle.

If we have value of and then the equation can be solved, which will give the last node’s location.

Finding 1. Detect the cycle using Floyd’s Cycle detection algorithm. (Two pointer with varying speed)
2. When cycle is detected
1. Store the current node as H
2. Move to next node and increment y(y++)
3. If current node is H then exit
4. Goto step 2

Finding Let’s first see the easiest way to solve this:

1. Have two pointers (p1, p2)
2. p1 = node 0
3. p2 = p1 + y nodes
4. if p1 == p2 then we found the result is 5. p1 = p1 + y nodes
6. goto step 3.

The complexity of this algorithm linear depends on . For example if is 10K and is 2 then number of node visits are > 20K. In other words the complexity is .

I believe it can be done in or with following method This following diagram captures state when the “tortoise and the hare” algorithm detects the cycle. Lets define few more variables at the time of cycle detection: is the total number of nodes tortoise traveled. is the total number of nodes hare traveled. can be defined as number of nodes before the ‘last node’ where c is the number of complete cycles hare covered. From this we can derive Using value of , can be derived. Using this formula can be found. With this value, the last node can be found by travelling nodes where T and H met.

Written by samueldotj

August 29th, 2013 at 3:35 pm

Posted in Uncategorized