将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

分析：
核心思想就是比较两个链表当前的 val ，谁小就把谁添到结果链表，再往后移一位，直到某条链表到终点，再把另一条链表直接加到结果链表即可

题解一：
while 形式

/** * 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 || l2 == null)
            return l1 != null ? l1 : l2;
        ListNode head =new ListNode(0);
        ListNode pre = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        while (l1 != null) {
            pre.next = l1;
            pre = pre.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            pre.next = l2;
            pre = pre.next;
            l2 = l2.next;
        }
        return head.next;
    }
}

题解二：
递归

/** * 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 || l2 == null)
            return l1 != null ? l1 : l2;
        ListNode head = null;
        if(l1.val <l2.val) {
            head = l1;
            head.next = mergeTwoLists(l1.next,l2);
        }else {
            head = l2;
            head.next = mergeTwoLists(l1,l2.next);
        }
        return head;
    }
}