using System;

public class Node

{

    public int key;

    public Node next;

    public Node(int _key)

    {

        key = _key;

    }

}

public class Program

{

    public static void Main()

    {       

        Node node = new Node(5);

        node.next = new Node(12);

        node.next.next = new Node(1);

        node.next.next.next = new Node(10);

        node.next.next.next.next = new Node(9);

        node.next.next.next.next.next = new Node(8);

        Print(node);

        Node newHeader = InsertionSort(node);

        Console.Write("\n");

        Print(newHeader);

    }

    private static Node InsertionSort(Node node)

    {

        Node sortedHeader = null;

        Node current = node;

        while(current != null)

        {           

            Node next = current.next;

            sortedHeader = InsertedHeader(sortedHeader, current);

            current = next;

        }

        return sortedHeader;

    }

    private static Node InsertedHeader(Node sortedHeader, Node newNode)

    {

        if(sortedHeader == null || sortedHeader.key > newNode.key)

        {

            newNode.next = sortedHeader;

            return newNode;

        }

        else

        {

            Node current = sortedHeader;

            while(current.next != null && current.next.key < newNode.key)

            {

                current = current.next;

            }

            newNode.next = current.next;

            current.next = newNode;

            return sortedHeader;

        }

    }

    private static void Print(Node node)

    {

        Node current = node;

        while(current != null)

        {

            Console.Write($"{current.key} ");

            current = current.next;

        }

    }

}