Skip to content

Instantly share code, notes, and snippets.

@gabhi
Last active August 1, 2018 19:58
Show Gist options
  • Save gabhi/11363820 to your computer and use it in GitHub Desktop.
Save gabhi/11363820 to your computer and use it in GitHub Desktop.
Detect and remove cycle in linked list
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
@sarb1208
Copy link

sarb1208 commented Aug 1, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment