合并两个有序链表 Merge Two Sorted Lists

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const mergeTwoLists = function(l1, l2) {
if(!l1){
return l2;
}

if(!l2){
return l1;
}

if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);

return l1;
}
else{
l2.next = mergeTwoLists(l1, l2.next);

return l2;
}
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const mergeTwoLists = function(l1, l2) {
if(!l1 || !l2){
return getRest(l1,l2);
}

let fakeHead = new ListNode(-1);
let currentNode = fakeHead;

while(l1 && l2){
let l1IsSmaller = l1.val < l2.val;
let newNode = l1IsSmaller ? new ListNode(l1.val) : new ListNode(l2.val);
currentNode.next = newNode;
currentNode = newNode;
if(l1IsSmaller){
l1 = l1.next;
}
else{
l2 = l2.next;
}
}
currentNode.next = getRest(l1,l2);
return fakeHead.next;
};

function getRest(l1,l2){
return !!l1 ? l1 : l2;
}