Linked List - Detect a Cycle in a linked list and Fix the cycle

[Kalyan]

Find whether or not there is a cylcle in a linked list? If so, Fix the cycle

To find cycles in a list, starting from some O (n^2) trival solutions, to the classic Flyod's Cycle Finding Algorithm (also known as the Hare and Tortoise approach, or the 2 pointer approach) and a asymptotic faster variant, to a list reversal technique (which I havent seen being used anywhere).

There are a few O(n lg n) solutions which I did not mentoin here. (If there is enought interest I will post this).

Lets look into a way to fix this cycle. Of Course, there are trivial O(n^2) solutions for this, but I will not go through this. I will discuss an O(n) solution in this post

Sol - Fixing the Cycle

A combination of the two O(n) cycle detecting algorithms (2 pointer approach and list reversal methods) will be used for this solution. Let's look into an illustrative solution

Fig (i) is how the orignal list (with a cycle) will look like. The goal is to fix the cycle. This can be done by finding N3 and setting N3->Next to NULL. The question is how to we find this.

N0 is the head.

Run one of the Two-Pointer cycle finding methods that I disscussed before on this list. The two pointers will meet somewhere inside the loop (3-4-5-......10-11-3). Lets call the node that the

pointers meet as N1. Once the two pointers meet, hold one of the pointers(P1) at N1 and let the other other pointer(P2) traverse the cycle once, while keeping a count of the number of

nodes in the cycle. Let the number of nodes in the cylce be x. Now, point pointer P2 to the head of the list (N0) and run the traverse the list until you find N1 while keeping a count of

the number of nodes from the head N0 to N1. Lets this number be y.

N0            N2
0--->1---->2---->3---->4---->5---->6
                 |                  |
                 |                  |
            N3  11< ---10<---9<---8 N1

      Fig (i)

Now Reverse the list. The list would look like Fig (ii)

N0            N2
0--->1—->2—->3< ----4<----5<----6
                 |              |
                 |              |
            N3  11--->10—->9—->8 N1

      Fig (ii)


After reversal get a count of nodes from N0 to N1. Let this number be z.

The idea is to get the number of nodes from N0 to N2. Once we have this, we can get the address of N2 and then traverse the list in the loop, until we find a Node whose next is N2 and then set it to NULL.

To solve this:

Our Variables: Number of Nodes from N0 to N1 before reversal = y Number of Nodes from N0 to N1 after reversal = z Number of Nodes in the loop = x Numver of Nodes from N0 to N2 = k

We need to solve for k. We have the following equation at hand. y + z = 2k + x (This equation could differ slightly if the number of nodes caluclated were inclusive of the nodes or not) k = (y + z - x) / 2