Related Topics：[Linked List]
Similar Questions:[Merge k Sorted Lists][Merge Sorted Array][Sort List][Shortest Word Distance II]

题目：Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

思路：

思路1：新建一个链表，然后比较两个链表中的元素值，把较小的那个链到新链表中，由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素，则直接另一个未完成的链表直接链入新链表的末尾。

java解法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 dummy= new ListNode(-1);
        ListNode res=dummy;
        while(l1!=null&&l2!=null) {
            if(l1.val<=l2.val) {
                dummy.next=l1;
                l1=l1.next;
            } else {
                dummy.next=l2;
                l2=l2.next;
            }
            dummy=dummy.next;
        }
        dummy.next=l1==null? l2:l1;
        return res.next;
    }
}

思路2：也可以使用递归的方法，即两个列表中较小的部分加上其他元素合并的结果。
java解法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(l2.next,l1);
            return l2;
        }
    }
}