using System;

public class Node

{

    public int val;

    public Node next;

    public Node(int _val)

    {

        val = _val;

    }

}

​

public class Program

{

    public static void Main()

    {

        //2 -> 5 -> 3 -> 8 -> 4

        Node head = new Node(2);

        head.next = new Node(5);

        head.next.next = new Node(3);

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

        //head.next.next.next.next = new Node(4);       

        print(head);

        Node newHead = mergeSort(head);

        print(newHead);

    }

    private static Node mergeSort(Node h)

    {

        if(h == null || h.next == null)

            return h;

        Node mid = getMiddle(h);

        Node rightAfterMid = mid.next;

        mid.next = null;

        var leftList = mergeSort(h);

        var rightList = mergeSort(rightAfterMid);

        return mergeSortedLists(leftList, rightList);

    }

    private static void Push(Node head, Node node)

    {

        Node current = head;

        Node previous = null;

        while(current != null)

        {

            previous = current;

            current = current.next;

        }

        if(previous != null)

            previous.next = node;

    }

    private static Node mergeSortedLists(Node leftList, Node rightList)

    {       

        if(leftList == null)

            return rightList;

        if(rightList == null)

            return leftList;

        Node currLeft = leftList;

        Node currRight = rightList;

        Node result = new Node(0);      

        while(currLeft != null && currRight != null)

        {

            if(currLeft.val < currRight.val)

            {               

                Push(result, new Node(currLeft.val));

                currLeft = currLeft.next;

            }

            else

            {

                Push(result, new Node(currRight.val));

                currRight = currRight.next;

            }           

        }

        if(currLeft != null)

        {

            Push(result, new Node(currLeft.val));

            currLeft = currLeft.next;

        }

        if(currRight != null)

        {

            Push(result, new Node(currRight.val));

            currRight = currRight.next;

        }       

        return result.next;

    }

    private static Node getMiddle(Node head)

    {

        if(head == null) return head;

        Node fastPtr = head.next;

        Node slowPtr = head;

        while(fastPtr != null)

        {

            fastPtr = fastPtr.next;

            if(fastPtr != null)

            {

                fastPtr = fastPtr.next;

                slowPtr = slowPtr.next;

            }

        }

        return slowPtr;

    }

    private static void print(Node node)

    {

        Node current = node;

        while(current != null)

        {

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

            current = current.next;

        }

        Console.WriteLine("");

    }

}