21 Merge Two Sorted Lists
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.
- With my approach, I just began a new linked list and used two different pointers to iterate through both elements while keeping track of the smallest one.
- My alg. uses O(1) space and O(N) time complexity, which is the best you can get, although the code could potentially be cleaner.
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
else if (!l2) return l1;
// check which end is greater
ListNode *newNode = nullptr;
ListNode *newNodeIter = nullptr;
ListNode *iter1 = l1, *iter2 = l2;
ListNode *prev1 = nullptr, *prev2 = nullptr;
// start us off
if (l1->val < l2->val) {
newNode= l1;
prev1 = iter1;
iter1 = iter1->next;
}
else {
newNode= l2;
prev2 = iter2;
iter2 = iter2->next;
}
newNodeIter = newNode;
while (iter1 && iter2) {
if (iter1->val < iter2->val) {
newNodeIter->next = iter1;
newNodeIter = iter1;
prev1 = iter1;
iter1 = iter1->next;
}
else {
newNodeIter->next = iter2;
newNodeIter = iter2;
prev2 = iter2;
iter2 = iter2->next;
}
}
// at this point either same size, or one is larger
if (!iter1 && iter2) {
// iter2 has large vals
prev1->next = iter2;
}
else if (iter1 && !iter2) {
prev2->next = iter1;
}
// else the same size
return newNode;
}
Last modified 3yr ago