递归做法

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        else if(list2 == null) {
            return list1;
        }
        else if(list1.val > list2.val) {
            list2.next = Merge(list1,list2.next);
            return list2;
        } else {
            list1.next = Merge(list1.next,list2);
            return list1;
        }
    }
}