Last active
August 1, 2018 19:58
-
-
Save gabhi/11363820 to your computer and use it in GitHub Desktop.
Detect and remove cycle in linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Node slow, fast, start; | |
fast = slow = head; | |
//PART I - Detect if a loop exists | |
while (true) | |
{ | |
// fast will always fall off the end of the list if it is linear | |
if (fast == null || fast.next == null) | |
{ | |
// no loop | |
return; | |
} | |
else if (fast == slow || fast.next == slow) | |
{ | |
// detected a loop | |
break; | |
} | |
else | |
{ | |
fast = fast.next.next; // move 2 nodes at at time | |
slow = slow.next; // move 1 node at a time | |
} | |
} | |
//PART II - Identify the node that is the start of the loop | |
fast = head; //reset one of the references to head of list | |
//until both the references are one short of the common element which is the start of the loop | |
while(fast.next != slow.next) | |
{ | |
fast = fast.next; | |
slow = slow.next; | |
} | |
start = fast.next; | |
//PART III - Eliminate the loop by setting the 'next' pointer | |
//of the last element to null | |
fast = start; | |
while(fast.next != start) | |
{ | |
fast = fast.next; | |
} | |
fast.next = null; //break the loop |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Here's the easiest solution ----->>> https://gist.github.com/sarb1208/a7e2551ab42330ff9e5b6960be1d5b8b