Ben Huang's Blog

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解題思路: 比較兩個linked list的數值，以第一個節點數值比較小的linked list當作為比較基礎list並與另外一個linked list做比較， 將節點數值較小者設為next的數值，然後將基礎list所有節點比較過。 

以下為遞迴解法

using System;

namespace Merge_Two_Sorted_Lists
{
    class Program
    {
        static void Main(string[] args)
        {

            ListNode l1 = new ListNode(1);
            l1.next = new ListNode(2);
            l1.next.next = new ListNode(4);

            ListNode l2 = new ListNode(1);
            l2.next = new ListNode(3);
            l2.next.next = new ListNode(4);

            var result = MergeTwoLists(l1, l2);
        }

        public static ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
            if (l1.val < l2.val)
            {
                l1.next = MergeTwoLists(l1.next, l2);
                return l1;
            }
            else
            {
                l2.next = MergeTwoLists(l1, l2.next);
                return l2;
            }
        }

        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }
    }
}