Merge Two Sorted Linked Lists

114.6k
0

Given heads of two sorted linked lists, merge both lists into one sorted linked list and return the head of the merged list.

Every node stores an integer value and a pointer to the next node. The final linked list must contain all nodes or values from both input lists in non-decreasing order.

Example 1

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

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

Explanation: Values from both sorted lists are arranged in non-decreasing order.

Example 2

Input: list1 = [], list2 = [0]

Output: [0]

Explanation: Only the second list contributes nodes to the merged result.

Brute Force Approach

In this approach, we collect all values from both linked lists into an array. After collecting the values, we sort the array in non-decreasing order.

Once the values are sorted, we create a new linked list by inserting the sorted values one by one. Although this approach does not take advantage of the fact that the input linked lists are already sorted, it is simple to implement and serves as a straightforward baseline solution.

Algorithm

  • Create an empty array to store the values from both linked lists, as combining the values in one place makes sorting them straightforward.

  • Traverse the first linked list and append each node's value to the array, so all values from the first sorted list are included.

  • Traverse the second linked list and append each node's value to the same array, giving a complete collection of values from both lists.

  • Sort the array in non-decreasing order, as the required result needs all values arranged from smallest to largest.

  • Create a new linked list using the sorted values, since each sorted array element needs to correspond to one node in the result.

  • Connect the newly created nodes in the same order as the sorted array, preserving the required non-decreasing sequence.

  • Return the head of the newly created linked list as the merged sorted result.

Dry Run

merge two sorted lists brute force

merge two sorted lists brute force

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int data;
Node* next;
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Function to merge sorted lists using value collection.
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
vector<int> values;
ListNode* current = list1;
// Collect values from first sorted list.
while (current != nullptr) {
values.push_back(current->data);
current = current->next;
}
current = list2;
// Collect values from second sorted list.
while (current != nullptr) {
values.push_back(current->data);
current = current->next;
}
sort(values.begin(), values.end());
ListNode dummy(0);
ListNode* tail = &dummy;
// Build merged linked list from sorted values.
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
return dummy.next;
}
};
// Function to create a linked list from an array.
ListNode* createList(vector<int>& arr) {
if (arr.empty()) return nullptr;
ListNode* head = new ListNode(arr[0]);
ListNode* current = head;
for (int index = 1; index < (int)arr.size(); index++) {
current->next = new ListNode(arr[index]);
current = current->next;
}
return head;
}
// Function to print linked list values.
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->data;
if (current->next != nullptr) cout << " ";
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr1 = {1, 2, 4};
vector<int> arr2 = {1, 3, 4};
ListNode* list1 = createList(arr1);
ListNode* list2 = createList(arr2);
Solution sol;
ListNode* head = sol.mergeTwoLists(list1, list2);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O((N + M) log(N + M)), sorting all collected values dominates traversal.

Space Complexity: O(N + M), array storage and newly created result nodes use linear extra memory.

Better Approach

Since both linked lists are already sorted, compare their current head nodes and choose the smaller node for the merged list. That node remains fixed, while its next pointer is connected to the result of recursively merging the remaining nodes.

If either list becomes empty, return the other list because its remaining nodes are already sorted. The recursion continues choosing nodes until a base case is reached, then the merged links are completed while the recursive calls return.

When both values are equal, choose the node from the first linked list, as shown in the dry run. This approach reuses the existing nodes and does not create a separate merged list.

Algorithm

  • Return list2 when list1 is empty, as there are no remaining nodes to compare and the second list is already sorted.

  • Return list1 when list2 is empty, for the same reason, since all remaining nodes from the first list can directly become part of the result.

  • Compare the values of the current head nodes, as the smaller value must appear first in the merged sorted list.

  • Choose list1 when its value is smaller or equal to list2, otherwise choose list2; choosing list1 on equality also keeps the ordering shown in the dry run.

  • Recursively merge the remaining part of the two lists and connect the returned node to the chosen node's next, since the rest of the merged portion must follow the currently selected smallest node.

  • Return the chosen node as the head of the current merged portion, as it contains the smallest available value at that stage.

Dry Run

recursive merge

recursive merge

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int data) { val = data; next = nullptr; }
};
class Solution {
public:
// Function to merge sorted lists using recursion.
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr) return list2;
if (list2 == nullptr) return list1;
if (list1->val <= list2->val) {
// Attach merged suffix after first list node.
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
// Attach merged suffix after second list node.
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
};
// Function to create a linked list from an array.
ListNode* createList(vector<int>& arr) {
if (arr.empty()) return nullptr;
ListNode* head = new ListNode(arr[0]);
ListNode* current = head;
for (int index = 1; index < (int)arr.size(); index++) {
current->next = new ListNode(arr[index]);
current = current->next;
}
return head;
}
// Function to print linked list values.
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->val;
if (current->next != nullptr) cout << " ";
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr1 = {1, 2, 4};
vector<int> arr2 = {1, 3, 4};
ListNode* list1 = createList(arr1);
ListNode* list2 = createList(arr2);
Solution sol;
ListNode* head = sol.mergeTwoLists(list1, list2);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N + M), every node is chosen once.

Space Complexity: O(N + M), recursion stack can contain one call per chosen node.

Optimal Approach

Since both linked lists are already sorted, we can merge them by comparing their current nodes one by one. A dummy node is used to simplify list construction, and a tail pointer tracks the last node of the merged list.

At each step, we attach the smaller node to the merged list and move the corresponding list pointer forward. Once one list becomes empty, the remaining part of the other list is directly attached because it is already sorted.

Algorithm

  • Create a dummy node and initialize a tail pointer to it, as the dummy node provides a fixed starting point while tail keeps track of where the next selected node should be attached.

  • Traverse both linked lists while neither list is empty, since a comparison is possible only when both lists still have a current node.

  • Compare the current values of both lists, as both lists are already sorted and the smaller value must be placed next in the merged list.

  • Attach the smaller node to tail and move the corresponding list pointer forward, since that node has now been placed and the next node from the same list becomes its new candidate.

  • Move tail to the newly attached node, so it always represents the last node of the merged list.

  • Continue until one of the lists becomes empty, as at that point no further comparison is possible or necessary.

  • Attach the remaining non-empty list directly to tail, since its nodes are already sorted and all of them are greater than or equal to the nodes already merged.

  • Return dummy->next as the head of the merged linked list, since the dummy node is only used to simplify the construction.

Dry Run

merge lists optimal

merge lists optimal

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int data) { val = data; next = nullptr; }
};
class Solution {
public:
// Function to merge sorted lists by relinking nodes.
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (list1 != nullptr && list2 != nullptr) {
if (list1->val <= list2->val) {
// Link smaller current node from first list.
tail->next = list1;
list1 = list1->next;
} else {
// Link smaller current node from second list.
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
// Attach remaining suffix from non-empty list.
tail->next = (list1 != nullptr) ? list1 : list2;
return dummy.next;
}
};
// Function to create a linked list from an array.
ListNode* createList(vector<int>& arr) {
if (arr.empty()) return nullptr;
ListNode* head = new ListNode(arr[0]);
ListNode* current = head;
for (int index = 1; index < (int)arr.size(); index++) {
current->next = new ListNode(arr[index]);
current = current->next;
}
return head;
}
// Function to print linked list values.
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->val;
if (current->next != nullptr) cout << " ";
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr1 = {1, 2, 4};
vector<int> arr2 = {1, 3, 4};
ListNode* list1 = createList(arr1);
ListNode* list2 = createList(arr2);
Solution sol;
ListNode* head = sol.mergeTwoLists(list1, list2);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N + M), each node is visited and linked once.

Space Complexity: O(1), only dummy and tail pointers use constant extra memory.

Interview follow-up Questions

Yes. The optimal iterative approach relinks existing nodes and uses only constant extra pointer space.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.8k
Linked List

Sort a Linked List Using Merge Sort

Given the head of a singly linked list, sort the linked list in non-decreasing order and return the head of the sorted linked list. Each node contains an integer value and a pointer to the next nod...

112.1k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order...

101.5k
Comments0