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