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;
}
}
}
