Merge Two Sorted Linked Lists — Problem Statement & Solution Guide

Linked ListEasyTwo Pointers

TimeO(n + m)

SpaceO(1)

Problem Description

You are provided with the head pointers of two singly linked lists, list1 and list2. Both lists are already sorted in non-decreasing order. Your task is to combine these two sequences into a single linked list that maintains the non-decreasing order of elements. The resulting list must be constructed by reusing the existing nodes from the input lists rather than allocating new nodes for the data values.

Return the head node of the merged linked list. If one of the input lists is empty, the function should return the head of the other list. If both lists are empty, return null.

DSA Pattern Breakdown

"Merge Two Sorted Linked Lists"

easy

WHY DOES IT MATTER?

The two‑pointer merge pattern is fundamental for any algorithm that combines pre‑sorted sequences, forming the backbone of merge sort, external sorting, and streaming data pipelines where memory is limited.

OPTIMIZATION CHALLENGE

The key insight is that you never need to look beyond the current heads of the two lists; by always attaching the smaller head, you guarantee global order while keeping the operation strictly O(1) per node.

REAL-WORLD CONNECTION

Think of merging two sorted event streams from different microservices into a single chronological log; the same pointer logic ensures events are ordered without buffering the entire streams.

During an interview, write a dummy head to simplify edge‑case handling, then remember to return dummy.next; after the loop, just link the non‑empty remainder—this avoids extra conditional checks and keeps the code clean.

COMPLEXITY AT A GLANCE

⏱ Time:O(n + m)

💾 Space:O(1)

Core Theory — Why This Approach?

Merging two sorted linked lists is a classic example of the two‑pointer technique, where each pointer walks through one list, always selecting the smaller current element to attach to the result. Because the input lists are already sorted, we can guarantee that the next smallest element is always at the head of one of the two lists, allowing us to build the merged list in a single linear pass without backtracking. A naive approach that concatenates the lists and then sorts the combined sequence would require O((n+m) log(n+m)) time and additional memory for sorting, which becomes prohibitive for large inputs and defeats the purpose of using linked structures that excel at O(1) insertions.

The optimal paradigm leverages in‑place pointer manipulation: we repeatedly compare the values at the heads of list1 and list2, link the smaller node to the tail of the merged list, and advance the corresponding pointer. This continues until one list is exhausted, after which the remaining nodes of the other list are appended directly. The algorithm runs in O(n+m) time, where n and m are the lengths of the two lists, and uses O(1) auxiliary space because it reuses existing nodes rather than allocating new ones. This approach scales linearly and preserves the memory efficiency inherent to linked lists.

Interview Questions on This Problem

Q1How would you merge k sorted linked lists efficiently, and what is its time complexity?

Use a min‑heap (priority queue) to always extract the smallest head among the k lists, attaching it to the merged list and pushing its next node into the heap. This yields O(N log k) time, where N is the total number of nodes, and O(k) extra space for the heap.

Q2Can you merge two sorted singly linked lists without using a dummy head node? What are the trade‑offs?

Yes, by first determining the head of the merged list via a direct comparison of the two list heads, then using a tail pointer to attach subsequent nodes. The trade‑off is slightly more conditional logic at the start, but it eliminates the dummy node, reducing constant‑factor overhead and making the code marginally more memory‑tight.

Q3Why is it safe to reuse the original nodes when merging, and when might you need to create new nodes instead?

Reusing nodes preserves O(1) extra space because the original list structures already contain the necessary memory layout; it's safe as long as the problem permits mutating the input lists. You would need to allocate new nodes if the original lists must remain unchanged (e.g., when they are shared elsewhere) or when working in immutable data structures.

Examples

Example 1

Input

list1 = [1, 3, 5], list2 = [2, 4, 6]

Output

[1, 2, 3, 4, 5, 6]

Explanation: Initialize a dummy head. Compare 1 (list1) and 2 (list2); 1 is smaller, so append node 1. Compare 3 (list1) and 2 (list2); 2 is smaller, so append node 2. Compare 3 (list1) and 4 (list2); 3 is smaller, so append node 3. Compare 5 (list1) and 4 (list2); 4 is smaller, so append node 4. Compare 5 (list1) and 6 (list2); 5 is smaller, so append node 5. List1 is exhausted, so append the remaining node 6 from list2. The final sequence is 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Example 2

Input

list1 = [], list2 = [7, 8, 9]

Output

[7, 8, 9]

Explanation: Since list1 is empty, the merged list is simply list2. The head of the result points to the node with value 7, followed by 8 and 9.

Example 3

Input

list1 = [1, 1, 1], list2 = [1, 1, 1]

Output

[1, 1, 1, 1, 1, 1]

Explanation: Both lists contain identical values. The algorithm alternates or appends based on the comparison logic (typically <=). Comparing 1 and 1, append the first 1. Comparing 1 and 1, append the second 1. This continues until all nodes from both lists are appended, resulting in a list of six nodes, each with value 1.

Example 4

Input

list1 = [10, 20, 30], list2 = [5, 15, 25]

Output

[5, 10, 15, 20, 25, 30]

Explanation: Compare 10 (list1) and 5 (list2); 5 is smaller, append 5. Compare 10 (list1) and 15 (list2); 10 is smaller, append 10. Compare 20 (list1) and 15 (list2); 15 is smaller, append 15. Compare 20 (list1) and 25 (list2); 20 is smaller, append 20. Compare 30 (list1) and 25 (list2); 25 is smaller, append 25. List2 is exhausted, so append the remaining node 30 from list1. The final sequence is 5 -> 10 -> 15 -> 20 -> 25 -> 30.

Constraints

The number of nodes in list1 is in the range [0, 50].
The number of nodes in list2 is in the range [0, 50].
-10^4 <= Node.val <= 10^4.
list1 and list2 are sorted in non-decreasing order.

Optimal Approach & Strategy

The optimal solution walks both lists simultaneously, always picking the smaller current node and linking it to the result. It finishes in O(n+m) time with O(1) auxiliary space by reusing the original nodes.

Brute Force Approach

A naive solution would concatenate list2 to the end of list1 and then sort the combined list using a generic sorting algorithm. This requires O((n+m) log(n+m)) time and extra space for sorting.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n + m)

function mergeTwoLists(list1, list2) { 
       let dummy = new ListNode(0); 
       let current = dummy; 
       while (list1 && list2) { 
           if (list1.val < list2.val) { 
               current.next = list1; 
               list1 = list1.next; 
           } else { 
               current.next = list2; 
               list2 = list2.next; 
           } 
           current = current.next; 
       } 
       current.next = list1 || list2; 
       return dummy.next; 
   }

class Solution { 
       public: 
           ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { 
               ListNode* dummy = new ListNode(0); 
               ListNode* current = dummy; 
               while (list1 && list2) { 
                   if (list1->val < list2->val) { 
                       current->next = list1; 
                       list1 = list1->next; 
                   } else { 
                       current->next = list2; 
                       list2 = list2->next; 
                   } 
                   current = current->next; 
               } 
               current->next = list1 ? list1 : list2; 
               return dummy->next; 
           } 
   }

class Solution { 
       public ListNode mergeTwoLists(ListNode list1, ListNode list2) { 
           ListNode dummy = new ListNode(0); 
           ListNode current = dummy; 
           while (list1 != null && list2 != null) { 
               if (list1.val < list2.val) { 
                   current.next = list1; 
                   list1 = list1.next; 
               } else { 
                   current.next = list2; 
                   list2 = list2.next; 
               } 
               current = current.next; 
           } 
           current.next = list1 == null ? list2 : list1; 
           return dummy.next; 
       } 
   }

class Solution: 
       def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode: 
           dummy = ListNode(0) 
           current = dummy 
           while list1 and list2: 
               if list1.val < list2.val: 
                   current.next = list1 
                   list1 = list1.next 
               else: 
                   current.next = list2 
                   list2 = list2.next 
               current = current.next 
           current.next = list1 or list2 
           return dummy.next

function mergeTwoLists(list1, list2) { 
       let dummy = new ListNode(0); 
       let current = dummy; 
       while (list1 && list2) { 
           if (list1.val < list2.val) { 
               current.next = list1; 
               list1 = list1.next; 
           } else { 
               current.next = list2; 
               list2 = list2.next; 
           } 
           current = current.next; 
       } 
       current.next = list1 || list2; 
       return dummy.next; 
   }

Asked in Top Tech Interviews

AmazonMicrosoftMeta

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.

Merge Two Sorted Linked Lists Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Linked List

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Merge Two Sorted Linked Lists — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor