Merge Two Sorted Lists — Problem Statement & Solution Guide
Problem Description
You are provided with two singly linked lists, each containing integer nodes arranged in non-decreasing order. The objective is to combine these two sequences into a single, unified linked list that maintains the non-decreasing property throughout. The resulting structure must preserve the relative order of elements from the original lists while ensuring global sortedness.
The input is represented as two arrays of integers, where each array corresponds to the sequential values of the respective linked list. Your task is to process these arrays and return a single array of integers that represents the values of the merged linked list in the correct sorted order. The merging process should be efficient, ideally operating in linear time relative to the total number of nodes in both input lists.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Merge Two Sorted Lists"
WHY DOES IT MATTER?
The merge pattern is fundamental because many complex problems decompose into sorted sub‑structures; mastering it enables you to build efficient pipelines for data aggregation, external sorting, and real‑time event merging, all of which are common in high‑throughput services.
OPTIMIZATION CHALLENGE
The key insight is to avoid any extra storage by re‑linking nodes in place; recognizing that the smallest head among the two lists must be the next element of the merged list eliminates the need for auxiliary arrays or recursive stack frames.
REAL-WORLD CONNECTION
Think of merging live transaction logs from two banking branches: each log is already time‑ordered, and the central ledger must reflect a single chronological sequence. The algorithm mirrors how distributed databases reconcile ordered logs without re‑sorting the entire dataset.
During an interview, start by writing a dummy head node, then walk both lists with a while loop, always moving the tail pointer forward. After the loop, simply attach the non‑empty list—this one‑liner often impresses interviewers because it shows both correctness and brevity.
COMPLEXITY AT A GLANCE
O(m + n)O(1)Core Theory — Why This Approach?
Merging two sorted linked lists is a classic example of the two‑pointer technique, a cornerstone of divide‑and‑conquer and greedy algorithms. By maintaining a pointer at the head of each list and repeatedly selecting the smaller current node, we can construct a new list in a single linear pass, guaranteeing that the global order remains non‑decreasing without any additional sorting. Naïve solutions—such as concatenating the lists and then applying a generic sort like quicksort or mergesort—require O((m+n) log(m+n)) time and extra space for array conversion, which becomes prohibitive when the input size grows to millions of nodes or when memory is constrained. The optimal paradigm leverages the inherent ordering of the inputs, achieving O(m+n) time and O(1) auxiliary space by re‑linking existing nodes rather than allocating new ones, thus preserving cache locality and minimizing garbage‑collector pressure in managed languages.
The optimal algorithm also exemplifies the concept of in‑place merging, a pattern that recurs in problems ranging from merging k‑sorted arrays to external‑memory sorting in distributed systems. By treating the output list as a mutable spine that we extend node by node, we avoid the overhead of auxiliary data structures and keep the algorithm deterministic—critical for interview settings where predictable performance is scrutinized. This approach scales gracefully: whether the lists are of equal length, highly imbalanced, or contain duplicate values, the two‑pointer loop adapts without additional branching, delivering a robust solution that aligns with real‑world engineering constraints.
Interview Questions on This Problem
Q1How would you merge two sorted singly linked lists without allocating new nodes, and what is the resulting time and space complexity?
Iterate with two pointers, compare current nodes, attach the smaller node to a dummy head, and advance the corresponding pointer. Continue until one list is exhausted, then link the remainder. This runs in O(m+n) time and O(1) extra space because we only rewire existing pointers.
Q2In a system that streams sorted data from two sources, how can you adapt the merge‑two‑lists algorithm to work with potentially infinite streams?
Treat each stream as an iterator that yields the next node on demand. Use the same two‑pointer comparison, but instead of reaching a null terminator, you wait for the next value from each stream. The algorithm remains O(1) per element and uses constant auxiliary space, making it suitable for unbounded data.
Q3Why might a recursive implementation of merging two sorted lists cause a stack overflow on large inputs, and how would you refactor it?
Recursion adds a call frame for each node, leading to O(m+n) stack depth, which can exceed language limits for large lists. Refactor by converting the recursion to an iterative loop that uses a dummy head and tail pointer, preserving the same O(m+n) time while keeping stack usage O(1).
Examples
Input
list1 = [1, 3, 5], list2 = [2, 4, 6]
Output
[1, 2, 3, 4, 5, 6]
Explanation: Compare the heads of both lists: 1 < 2, so append 1. Next, compare 3 and 2: 2 < 3, so append 2. Then compare 3 and 4: 3 < 4, so append 3. Continue this process: 4 < 5, append 4; 5 < 6, append 5; finally, append the remaining 6. The final sequence is [1, 2, 3, 4, 5, 6].
Input
list1 = [], list2 = [7, 8, 9]
Output
[7, 8, 9]
Explanation: Since the first list is empty, the merged list is simply the second list itself. No comparisons are needed, and the output directly reflects the values of list2.
Input
list1 = [1, 1, 1], list2 = [1, 1, 1]
Output
[1, 1, 1, 1, 1, 1]
Explanation: Both lists contain identical values. The merge process alternates or appends elements as they are encountered. Since all values are equal, the order of selection between lists does not affect the final sorted output, which consists of six 1s.
Input
list1 = [10, 20, 30], list2 = [5, 15, 25]
Output
[5, 10, 15, 20, 25, 30]
Explanation: Start by comparing 10 and 5: 5 is smaller, so append 5. Next, compare 10 and 15: 10 is smaller, so append 10. Then compare 20 and 15: 15 is smaller, so append 15. Continue: 20 < 25, append 20; 30 > 25, append 25; finally, append the remaining 30. The result is [5, 10, 15, 20, 25, 30].
Constraints
- 0 <= list1.length <= 10^4
- 0 <= list2.length <= 10^4
- -10^9 <= list1[i], list2[i] <= 10^9
- list1 and list2 are sorted in non-decreasing order
Optimal Approach & Strategy
Use two pointers to traverse both lists simultaneously, always linking the smaller current node to the merged list, and finally attach any remaining nodes from the non‑exhausted list.
Brute Force Approach
Concatenate the two lists, copy all node values into an array, sort the array, and rebuild a new linked list from the sorted array.
Verified Code Solutions
function mergeTwoLists(l1, l2) {
let dummy = new ListNode(0);
let current = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
if (l1 !== null) {
current.next = l1;
} else {
current.next = l2;
}
return dummy.next;
}class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
current->next = l1 ? l1 : l2;
return dummy->next;
}
}class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 == null ? l2 : l1;
return dummy.next;
}
}class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.nextfunction mergeTwoLists(l1, l2) {
let dummy = new ListNode(0);
let current = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
if (l1 !== null) {
current.next = l1;
} else {
current.next = l2;
}
return dummy.next;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.