hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Merge Two Sorted Lists
Problem: 21. Merge Two Sorted Lists
Problem Link:
Companies Asked: Uber, Adobe, Amazon, Oracle, Google, Shopee, Facebook, Microsoft, Bloomberg, Accenture, Apple
Approach:
Traverse the given linked lists one by one node.
Check which node has a lesser value.
Add the node with the lesser value to the other linked list that will be returned as an answer.
If one of the lists becomes empty add the current head of another non-empty list to the next node of the answer.
Keep doing until both of them gets empty.
Return the answer.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1)
Code [C++]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* first, ListNode* second) {
if(!first) return second;
if(!second) return first;
ListNode * ans, * ansCur, * curFirst, *curSecond;
if(first->val <= second->val){
curFirst = first->next;
curSecond = second;
ans = ansCur = first;
}
else{
curFirst = first;
curSecond = second->next;
ans = ansCur = second;
}
while(curFirst || curSecond){
if(!curSecond){
ansCur->next = curFirst;
break;
}
else if(!curFirst){
ansCur->next = curSecond;
break;
}
else if(curFirst->val <= curSecond->val){
ansCur->next = curFirst;
curFirst = curFirst->next;
}
else{
ansCur->next = curSecond;
curSecond = curSecond->next;
}
ansCur = ansCur->next;
}
return ans;
}
};