using System;

public class Program

{

    public static void Main()

    {

        var listNode1 = new ListNode(1, new ListNode(2, new ListNode(4)));

        var listNode2 = new ListNode(1, new ListNode(3, new ListNode(4)));

        var result = new ListsMerger().Merge(listNode1, listNode2);

        PrintListNode(result);

    }

    public static void PrintListNode(ListNode listNode)

    {

        while(listNode != null)

        {

            Console.WriteLine(listNode.val);

            listNode = listNode.next;

        }

    }

}

​

public class ListsMerger

{

    public ListNode Merge(ListNode listNode1, ListNode listNode2)

    {

        ListNode result;

        ListNode tmpListNode;

        if (listNode1.val < listNode2.val)

        {

            tmpListNode = listNode1;

            listNode1 = listNode1.next;

        }

        else

        {

            tmpListNode = listNode2;

            listNode2 = listNode2.next;

        }

        result = tmpListNode;

        while(listNode1 != null || listNode2 != null)

        {

            //Console.WriteLine("listNode1: " + listNode1.val + " " + "listNode2: "+ listNode2.val);

            if(listNode1 == null && listNode2 != null)

            {

                tmpListNode.next = listNode2;

                listNode2 = listNode2.next;

            }

            else if(listNode2 == null && listNode1 != null)

            {

                tmpListNode.next = listNode1;

                listNode1 = listNode1.next;

            }

            else if (listNode1.val < listNode2.val)

            {

                tmpListNode.next = listNode1;

                listNode1 = listNode1.next;

            }

            else

            {

                tmpListNode.next = listNode2;

                listNode2 = listNode2.next;

            }

            tmpListNode = tmpListNode.next;

        }

        return result;

    }

}

​

public class ListNode {

     public int val;

     public ListNode next;

     public ListNode(int val=0, ListNode next=null) 

     {

         this.val = val;

         this.next = next;

     }

}