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：新建一個(gè)鏈表，然后比較兩個(gè)鏈表中的元素值绽慈，把較小的那個(gè)鏈到新鏈表中盆佣，由于兩個(gè)輸入鏈表的長(zhǎng)度可能不同，所以最終會(huì)有一個(gè)鏈表先完成插入所有元素陨舱，則直接另一個(gè)未完成的鏈表直接鏈入新鏈表的末尾翠拣。
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：也可以使用遞歸的方法，即兩個(gè)列表中較小的部分加上其他元素合并的結(jié)果游盲。
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;
}
}
}
