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.



Example:
Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

https://leetcode.com/problems/merge-two-sorted-lists/description/

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
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode * p = NULL;
ListNode * l3 = new ListNode(-1); // create a new node
p = l3; // use to traverse

if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
if(l1 == NULL && l2 == NULL) return NULL;

while(l1 && l2) {
if( l1->val >= l2->val){ // add smaller node into l3
p->next = l2;
p = l2; // move to the newest node in l3
l2 = l2->next;
}
else {
p->next = l1;
p = l1;
l1 = l1->next;
}
if(!l1) p ->next = l2;
if(!l2) p ->next = l1;
}
return l3->next;
}
};
  1. Merge k Sorted Lists
  2. sort list