using System;

using System.Collections.Generic;

​

public class Program

{

    public static void Main()

    {

        LinkedList<int> ll = new LinkedList<int>();

        var root = ll.AddFirst(5);

        var curr = root;

        curr = ll.AddAfter(curr, 2);        

        curr = ll.AddAfter(curr, 3);

        curr = ll.AddAfter(curr, 7);

        curr = ll.AddAfter(curr, 1);

        curr = ll.AddAfter(curr, 6);

        curr = ll.AddAfter(curr, 4);

        Console.WriteLine("----------- List ----------------");

        Display(root);

        Console.WriteLine("--------Sorted List -------------");

        Display(Sort(ll).First);

    }

    public static LinkedListNode<int> FindSmallest(LinkedListNode<int> pointer){ //LinkedList<int> ll

        //var pointer = ll.First; // root

        LinkedListNode<int> small = pointer;

        while (pointer != null)

        {

            if(small.Value >= pointer.Value)

                small = pointer;

            pointer = pointer.Next;

        }

        return small;

    }

    public static LinkedList<int> Sort(LinkedList<int> ll) {

        LinkedList<int> sortedLl = new LinkedList<int>();

        var currSortedNode = sortedLl.First;

        var pointer = ll.First;

        while(pointer != null && ll.Count > 0){

            pointer = ll.First;

            var small =  FindSmallest(pointer);

            if(currSortedNode == null)

                currSortedNode = sortedLl.AddFirst(small.Value);

            else

                currSortedNode = sortedLl.AddAfter(currSortedNode,small.Value);

            ll.Remove(ll.Find(small.Value));                            

        }

        return sortedLl;

    }

    /*

    public static LinkedListNode<int> FindSmallest(LinkedListNode<int> pointer){ //LinkedList<int> ll

        //var pointer = ll.First; // root

        LinkedListNode<int> small = pointer;

        while (pointer != null)

        {

            if(small.Value >= pointer.Value)

                small = pointer;

            pointer = pointer.Next;

        }

        return small;

    }

    */

​

    public static void Display(LinkedListNode<int> pointer)

    {

        while (pointer != null)

        {

            Console.WriteLine(pointer.Value.ToString());

            pointer = pointer.Next;

        }

    }

}