algoadvance

Leetcode 21. Merge Two Sorted Lists

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example

Input:

list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

Output:

1 -> 1 -> 2 -> 3 -> 4 -> 4

Clarifying Questions

1. What if both lists are empty?
   • Return an empty list.
2. What if one of the lists is empty?
   • Return the non-empty list.

Strategy

1. Use a dummy head to simplify the merge process.
2. Use two pointers to traverse each list.
3. Compare the current nodes of list1 and list2:
   • Append the smaller one to the result list.
   • Move the corresponding pointer forward.
4. Continue this process until one of the lists is fully traversed.
5. Append the remaining nodes of the non-empty list to result list.
6. Return the next of the dummy head as the result (to discard the initial dummy node).

Code

// 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) {
        // Create a dummy node to provide easy manipulation of new list
        ListNode dummy;
        ListNode* tail = &dummy;

        // Traverse both lists
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }

        // Attach the remaining nodes, if any
        if (list1 != nullptr) {
            tail->next = list1;
        } else {
            tail->next = list2;
        }

        // Return the head of the merged list
        return dummy.next;
    }
};

Time Complexity

• The time complexity of this algorithm is O(n + m), where n is the number of nodes in list1 and m is the number of nodes in list2. This is because we traverse each list exactly once.
• The space complexity is O(1) (excluding the space needed for the input lists), as we are only using a few additional pointers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?