using System;

public class Program

{

    public static void Main()

    {

        Node<int> node1 = MergeLinkedLists_Node1();

        Node<int> node2 = MergeLinkedLists_Node2();

        Print(node1, "Node1 is:  ");

        Console.WriteLine("");

        Print(node2, "Node2 is:  ");

        Console.WriteLine("");

        Console.WriteLine("");

        var res = MergeList(node1, node2);

        Print(res, "After Merge:  ");

    }

    private static Node<int> MergeList(Node<int> a, Node<int> b)

    {

        if (a == null)

            return b;

        else if (b == null)

            return a;

        else if (a == null || b == null)

            return null;

​

        Node<int> retNode = null;

        if (a.data > b.data)

        {

            retNode = b;

            retNode.next = MergeList(a, b.next);

        }

        else

        {

            retNode = a;

            retNode.next = MergeList(a.next, b);

        }

        return retNode;

    }

    private static Node<int> MergeLinkedLists_Node1()

    {

        Node<int> node = new Node<int>();

        node.data = 1;

        node.next = new Node<int>();

        node.next.data = 3;

        node.next.next = new Node<int>();

        node.next.next.data = 5;

        node.next.next.next = new Node<int>();

        node.next.next.next.data = 7;

        node.next.next.next.next = null;

        return node;

    }

​

    private static Node<int> MergeLinkedLists_Node2()

    {

        Node<int> node = new Node<int>();

        node.data = 2;

        node.next = new Node<int>();

        node.next.data = 4;

        node.next.next = new Node<int>();

        node.next.next.data = 6;

        node.next.next.next = new Node<int>();

        node.next.next.next.data = 8;

        node.next.next.next.next = null;

        return node;

    }

    private static void Print(Node<int> node, string str)

    {

     Console.Write(str);

     while(node != null)

     {

      Console.Write(node.data + " --> ");

      node = node.next;

     }

     Console.Write("null");

    }

}

​

public class Node<T>

{

   public Node<T> next;

   public T data;

   public Node()

   {

   }

​

   public Node(T obj)

   {

    data = obj;

   }

}