Notes

21. Merge Two Sorted Lists

3 min read

Prompt

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

Merge the two lists into 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.

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

Examples

  • Example 1:
    • Input: list1 = [1,2,4], list2 = [1,3,4]
    • Output: [1,1,2,3,4,4]
  • Example 2:
    • Input: list1 = [], list2 = []
    • Output: []
  • Example 3:
    • Input: list1 = [], list2 = [0]
    • Output: [0]

Solutions

Basic Solution

In C++

inline void push_back(ListNode *& head, ListNode *& tail, ListNode *& val_node) {
    if (!tail) {
        tail = new ListNode(val_node->val);
        head = tail;
    } else {
        tail->next = new ListNode(val_node->val);
        tail = tail->next;
    }
    val_node = val_node->next;
}
ListNode * mergeTwoLists(ListNode * list1, ListNode * list2) {
	ListNode * head = nullptr;
	ListNode * tail = nullptr;
 
	if (!list1 && !list2) return head;
	if (!list1) return list2;
	if (!list2) return list1;
 
	while (list1 && list2) push_back(head, tail, (list1->val < list2->val) ? list1 : list2);
	while (list1) push_back(head, tail, list1);
	while (list2) push_back(head, tail, list2);
 
	return head;
}

Explanation

The high level idea here is very simple. Insert the lesser element from either list, while they both still have elements left. After that, empty the remaining one into the output list.

Big O Analysis

Time Complexity

Auxiliary Space Complexity

Dummy Node Solution

In C++

inline void push_back(ListNode *& tail, ListNode *& val_node) {
    tail->next = new ListNode(val_node->val);
    tail = tail->next;
    val_node = val_node->next;
}
ListNode * mergeTwoLists(ListNode * list1, ListNode * list2) {
	if (!list1 && !list2) return nullptr;
	if (!list1) return list2;
	if (!list2) return list1;
	
	ListNode * dummy = new ListNode(0);
	ListNode * tail = dummy;
 
	while (list1 && list2) push_back(tail, (list1->val < list2->val) ? list1 : list2);
	while (list1) push_back(tail, list1);
	while (list2) push_back(tail, list2);
 
	ListNode * head = dummy->next;
	delete dummy;
	return head;
}

Explanation

Same as Basic Solution but uses a dummy node.

Big O Analysis

Time Complexity

Auxiliary Space Complexity

Juggling Solution

In C++

ListNode * mergeTwoLists(ListNode * list1, ListNode * list2) {
	if (!list1 && !list2) return nullptr;
	if (!list1) return list2;
	if (!list2) return list1;
	
	ListNode * dummy = new ListNode(0);
	ListNode * tail = dummy;
 
	while (list1 && list2) {
		ListNode *& node = (list1->val < list2->val) ? list1 : list2;
		tail->next = node;
		tail = tail->next;
		node = node->next;
	}
 
	tail->next = list1 ? list1 : list2;
 
	ListNode * head = dummy->next;
	delete dummy;
	return head;
}

Explanation

We modify the Dummy Node Solution to have optimal space complexity by juggling the linked lists between the output list. We can do this because we don’t actually care about destroying the inputs. All we care about is the output being correct and the complexity being good.

Note also that at the end, instead of repeatedly, inserting the final elements into the list like we would if the inputs were Arrays, we can actually just add the entire remaining list all at once, in a single assignment. This only works because we are using Linked Lists

Big O Analysis

Time Complexity

Auxiliary Space Complexity

, because our “Juggling” makes the solution In-place

Graph View