Write a program to sort link list using Merge Sort

Solution:

using System;

namespace LinkedListOpearation
{

    class Program
    {
        public static void Main()
        {
            var linkedList = new LinkedList();
            linkedList.Add(15);
            linkedList.Add(10);
            linkedList.Add(5);
            linkedList.Add(20);
            linkedList.Add(3);
            linkedList.Add(2);

            linkedList.Head = linkedList.MergeSort(linkedList.Head);
            Console.WriteLine("Sorted Linked List is:");
            linkedList.Print(linkedList.Head);
            Console.ReadLine();
        }   
    }

    
    public class LinkedList
    {
        public Node Head;
      
        public Node SortedMerge(Node node1, Node node2)
        {
            Node result;
            if (node1 == null)
                return node2;
            if (node2 == null)
                return node1;

            if (node1.Data <= node2.Data)
            {
                result = node1;
                result.Next = SortedMerge(node1.Next, node2);
            }
            else
            {
                result = node2;
                result.Next = SortedMerge(node1, node2.Next);
            }
            return result;
        }

        public Node MergeSort(Node node)
        {
            if (node?.Next == null)
            {
                return node;
            }

            var intermediate = GetIntermediate(node);
            var next = intermediate.Next;

            intermediate.Next = null;
            var left = MergeSort(node);
            var right = MergeSort(next);
            return SortedMerge(left, right);
        }


        public Node GetIntermediate(Node node)
        {
            if (node == null)
                return null;

            var currentNode = node.Next;
            var nextNode = node;

            while (currentNode != null)
            {
                currentNode = currentNode.Next;
                if (currentNode == null) continue;
                nextNode = nextNode.Next;
                currentNode = currentNode.Next;
            }
            return nextNode;
        }

        public void Add(int data)
        {
            var node = new Node(data) {Next = Head};
            Head = node;
        }

        public void Print(Node head)
        {
            while (head != null)
            {
                Console.WriteLine(head.Data);
                head = head.Next;
            }
        }
    }

    public class Node
    {
        public int Data;
        public Node Next;

        public Node(int data)
        {
            Data = data;
        }
    }
}