Sunday, 15 January 2017

Detect a Loop in Singly Linked List and Remove Loop

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
            }
        }
    }
}

No comments:

Post a Comment