Merge Two Sorted Lists

The algorithm is designed to merge two sorted linked lists into a single sorted linked list. It operates by comparing elements from both lists, appending the smaller element to the merged list, and advancing the pointer in the corresponding list. This process continues until one of the lists is exhausted.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

Approach

We explore an efficient approach to merge two sorted linked lists in C++. We leverage a dummy node and maintain a pointer to the current node in the merged list. By iterating through both lists, we compare elements and link nodes in ascending order. We handle remaining elements if one list is longer than the other, ensuring a fully merged and sorted result.

/**
 * 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* list1, ListNode* list2) {
            ListNode* dummy = new ListNode(0);
            ListNode* current = dummy;
        while(list1 != nullptr && list2 != nullptr){
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
             // If one of the lists is not empty, append the remaining elements
            if (list1 != nullptr) {
                current->next = list1;
            } else if (list2 != nullptr) {
                current->next = list2;
            }
            // Return the merged list starting from the next of the dummy node
            return dummy->next;
    }
};

• Time Complexity: O(m + n) - Linear time complexity, as the algorithm iterates through both linked lists once.
• Auxiliary Space: O(1) - Constant auxiliary space, indicating a fixed amount of additional memory used, irrespective of the input list sizes.