21. Merge Two Sorted Lists

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: l1 = [], l2 = []
Output: []
Input: l1 = [], l2 = [0]
Output: [0]
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

vector<int> v;

v.clear();

while(l1 != NULL && l2 != NULL){

if(l1->val == l2->val){
v.push_back(l1->val);
v.push_back(l2->val);
l1 = l1->next;
l2 = l2->next;
if(l1 == NULL || l2 == NULL){
break;
}

}

if(l1->val > l2->val){
v.push_back(l2->val);
l2 = l2->next;
if(l1 == NULL || l2 == NULL){
break;
}

}
if(l1->val < l2->val){
v.push_back(l1->val);
l1 = l1->next;
if(l1 == NULL || l2 == NULL){
break;
}

}
}

while(l1!= NULL){
v.push_back(l1->val);
l1 = l1->next;
}

while(l2!= NULL){
v.push_back(l2->val);
l2 = l2->next;
}

ListNode *merge = NULL;
ListNode *now = NULL;
for(int i=0; i<v.size(); i++){
ListNode *tmp = new ListNode();
tmp->val = v[i];
if(i == 0){
merge = tmp;
now = merge;
}
else{
now->next = tmp;
now = tmp;
}
}

return merge;

}
};
  1. compare l1->val and l2->val, whose value is bigger then push it into vector and go to the next node.
  2. if one of the linked list is NULL, push all the nodes value in another linked list into the vector, vice versa.
  3. return the head of the merge linked list.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store