21. 合并兩個(gè)有序鏈表
將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
/**
* 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;
}
ListNode result = l1;
ListNode l1Loop = l1;
ListNode l2Loop = l2;
if (l1Loop.val > l2Loop.val) {
l1 = result = l2Loop;
l2Loop = l2Loop.next;
} else {
l1Loop = l1Loop.next;
}
while (l1Loop != null) {
while (l2Loop != null) {
if (l1Loop.val > l2Loop.val) {
result.next = l2Loop;
result = result.next;
l2Loop = l2Loop.next;
} else {
break;
}
}
result.next = l1Loop;
result = result.next;
l1Loop = l1Loop.next;
}
while (l2Loop != null) {
result.next = l2Loop;
result = result.next;
l2Loop = l2Loop.next;
}
return l1;
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度 : O(m+n)
空間復(fù)雜度 : O(1)
