-
Notifications
You must be signed in to change notification settings - Fork 0
/
Merge Two Sorted List
47 lines (36 loc) · 1013 Bytes
/
Merge Two Sorted List
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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, and should also be sorted.
For example, given following linked lists :
5 -> 8 -> 20
4 -> 11 -> 15
The merged list should be :
4 -> 5 -> 8 -> 11 -> 15 -> 20
//Soltuon #1
____________
ListNode* callMerge(ListNode*A,ListNode*B){
if(A==nullptr){
return B;
}
if(B==nullptr){
return A;
}
if(A->val<=B->val){
A->next = callMerge(A->next,B);
return A;
}else{
B->next = callMerge(B->next,A);
return B;
}
}
ListNode* Solution::mergeTwoLists(ListNode* A, ListNode* B) {
if (A->val > B->val) std::swap(A,B);
callMerge(A,B);
return A;
}
//Solution #2
_____________
ListNode<int> * mergeTwoLinkedLists(ListNode<int> * l1, ListNode<int> * l2) {
if(!l1||(l2 && (l1->value > l2->value))) swap(l1,l2);
if(l1) l1->next = mergeTwoLinkedLists(l1->next, l2);
return l1;
}