using System;

​

namespace husoAkvelon2

{

    public class Node

    {

        public int data;

        public Node next;

        public Node(int data)

        {

            this.data = data;

            this.next = null;

        }

    }

​

    public class OneWayLinkedList

    {

        private Node start;

        private Node loopStart;

        //this method will create wanted loop between 7 and 3

        public void CreateLoopForTest()

        {

            start.next.next.next.next = start.next;

        }

​

        public bool CheckForLoop()

        {

            Node oneIncrement = start;

            Node twoIncrement = start;

​

            while (oneIncrement != null && twoIncrement != null && twoIncrement.next != null)

            {

                oneIncrement = oneIncrement.next;

                twoIncrement = twoIncrement.next.next;

                if (oneIncrement == twoIncrement)

                {

                    loopStart = GetLoopStartNode(twoIncrement);

                    return true;

                }

            }

            return false;

        }

​

        private Node GetLoopStartNode(Node twoIncrement)

        {

            Node oneIncrement = start;

            while (oneIncrement != twoIncrement)

            {

                oneIncrement = oneIncrement.next;

                twoIncrement = twoIncrement.next;

            }

​

            return oneIncrement;

        }

​

        public void AddAndPreserveOrder(int data)

        {

            Node newNode = new Node(data);

            if (start == null)

            {

                start = newNode;

                return;

            }

​

            if (data <= start.data)

            {

                newNode.next = start;

                start = newNode;

                return;

            }

​

            //Must check if the loop exist - when the loop is found, we will not check it anymore

            if (loopStart == null) CheckForLoop();

​

            Node current = loopStart == null ?

                start : data <= loopStart.data ?

                start : loopStart;

            var next = current.next;

            while (next != loopStart)

            {

                if (data <= next.data)

                {

                    current.next = newNode;

                    newNode.next = next;

                    return;

                }

                current = current.next;

                next = next.next;

            }

            current.next = newNode;

            newNode.next = loopStart;

        }

        public void PrintElements()

        {

            var temp = start;

            while (temp != null)

            {

                Console.Write("{0} ", temp.data);

                temp = temp.next;

            }

        }

​

    }

​

    public class Program

    {

        public static void Main(string[] args)

        {

            OneWayLinkedList list = new OneWayLinkedList();

​

            //order will be ascending

            list.AddAndPreserveOrder(3);

            list.AddAndPreserveOrder(5);

            list.AddAndPreserveOrder(7);

            list.AddAndPreserveOrder(2);

            //this method creates loop between 7 and 3

            list.CreateLoopForTest();

            //adding more elements

            list.AddAndPreserveOrder(6);

            list.AddAndPreserveOrder(8);

            list.AddAndPreserveOrder(-1);

            list.AddAndPreserveOrder(3);

            list.AddAndPreserveOrder(0);

            list.AddAndPreserveOrder(4);

            list.PrintElements();

        }

    }

}

​