using System;

​

public class Program

{

    public static void Main(string[] args)

    {

        var first = new Node(15);

        first.Push(10).Push(5).Push(20).Push(3).Push(2);

        first.Print();

        var sorted = MergeSort(first);

        Console.WriteLine("=============== After sorting ===============");

        sorted.Print();

    }

​

    static Node Merge(Node first, Node second)

    {

        Node result = null;

        if (first == null)

        {

            return second;

        }

        else if (second == null)

        {

            return first;

        }

​

        if (first.Data < second.Data)

        {

            result = first;

            result.Next = Merge(first.Next, second);

        }

        else

        {

            result = second;

            result.Next = Merge(first, second.Next);

        }

​

        return result;

    }

​

    static Node MergeSort(Node node)

    {

        if (node.Next == null)

        {

            return node;

        }

​

        var middle = GetMiddle(node);

        var nextToMiddle = middle.Next;

        middle.Next = null;

        node = MergeSort(node);

        nextToMiddle = MergeSort(nextToMiddle);

        var sortedLinkedList = Merge(node, nextToMiddle);

        return sortedLinkedList;

    }

​

    static Node GetMiddle(Node node)

    {

        if (node?.Next == null)

        {

            return node;

        }

​

        var fastPointer = node.Next;

        var slowPointer = node;

        while (fastPointer != null)

        {

            fastPointer = fastPointer.Next;

            if (fastPointer != null)

            {

                fastPointer = fastPointer.Next;

                slowPointer = slowPointer.Next;

            }

        }

​

        return slowPointer;

    }

}

​

public class Node

{

    public int Data

    {

        get;

        set;

    }

​

    public Node Next

    {

        get;

        set;

    }

​

    public Node(int data)

    {

        this.Data = data;

        this.Next = null;

    }

​

    public void Print()

    {

        var node = this;

        do

        {

            Console.Write(node.Data + " ");

            node = node.Next;

        }

        while (node != null);

        Console.WriteLine();

    }

​

    public int GetLengthIterative()

    {

        var node = this;

        var count = 0;

        while (node != null)

        {

            count++;

            node = node.Next;

        }

​

        return count;

    }

​

    public int GetLengthRecursive()

    {

        if (this.Next == null)

        {

            return 1;

        }

​

        return 1 + this.Next.GetLengthRecursive();

    }

​

    public Node Push(int data)

    {

        var node = new Node(data);

        this.Next = node;

        return node;

    }

​

    public override string ToString()

    {

        return Data.ToString();

    }

}