using System;
namespace ConsoleApplication1
{
class Program
{
public class LinkedListNode
{
public LinkedListNode() { }
public LinkedListNode(T value)
{
Value = value;
}
public T Value { get; set; }
public LinkedListNode Next { get; set; }
}
static void Main(string[] args)
{
LinkedListNode Llist = new LinkedListNode();
Llist.Next = new LinkedListNode(1);
Llist.Next.Next = new LinkedListNode(2);
Llist.Next.Next.Next = new LinkedListNode(3);
Llist.Next.Next.Next.Next = new LinkedListNode(4);
Llist.Next.Next.Next.Next.Next = new LinkedListNode(5);
Llist.Next.Next.Next.Next.Next.Next = new LinkedListNode(6);
Llist.Next.Next.Next.Next.Next.Next.Next = Llist.Next.Next.Next.Next;
Console.WriteLine(FloydCycleDedection(Llist).ToString());
Console.WriteLine(FloydCycleDedection(Llist).ToString());
Console.Read();
}
public static bool FloydCycleDedection(LinkedListNode node)
{
LinkedListNode slow = node, fast = node;
while (slow != null && fast != null && fast.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
if (slow == fast)
{
removeLoop(node, slow, fast);
return true;
}
}
return false;
}
public static void removeLoop(LinkedListNode node, LinkedListNode slow, LinkedListNode fast)
{
/* If loop exists */
if (slow == fast)
{
slow = node;
while (slow != fast.Next)
{
slow = slow.Next;
}
fast.Next = null; // remove loop
}
}
}
}
Sunday, 15 January 2017
Detect a Loop in Singly Linked List and Remove Loop
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment