合并两个排序的链表

1、迭代 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head_one = l1;
        ListNode head_two = l2;
        ListNode result = new ListNode(-1);
        ListNode res = result;
        while(head_one != null && head_two != null){
            if(head_one.val <= head_two.val){
                result.next = head_one;
                head_one = head_one.next;
            }
            else{
                result.next = head_two;
                head_two = head_two.next;
            }
            result = result.next;
        }
        result.next = (head_one == null ? head_two : head_one);
        return res.next;
    }
}

时间复杂度：O(m+n)，空间复杂度：O(N)，N为常量 

2、递归 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public 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;
        }
    }
}

时间复杂度：O(m+n)，空间复杂度：O(m+n)