EasyLinked ListRecursionUpdated Sep 2026

21. Merge Two Sorted Lists

Asked at Amazon, Microsoft, Adobe, Oracle and 2 more

Difficulty

Easy

Time

O(m + n)

Space

O(1)

Pattern

Linked List

Companies

6

Problem

You get the heads of two linked lists, list1 and list2. Each list is already sorted in non-decreasing order (small values first, equal values allowed next to each other).

Join the two lists into one sorted linked list. Do this by re-linking the existing nodes — do not create new nodes with copied values. The result must also be sorted in non-decreasing order.

Return the head node of the merged list. If both lists are empty, return null.

Two sorted lists, one sorted result

list1124nulllist1 is already sorted: 1 → 2 → 4list2134nulllist2 is already sorted: 1 → 3 → 4merged112344nullThe merged list keeps every node and stays sorted.
We must weave the two sorted chains into a single sorted chain using the same nodes.

Constraints

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

Examples

Example 1
Inputlist1 = [1,2,4], list2 = [1,3,4]
Output[1,1,2,3,4,4]
WhyWe repeatedly take the smaller front node. 1 vs 1 → take the first 1, then the second 1, then 2, then 3, then 4, then 4. The result is sorted and uses all six nodes.
Example 2
Inputlist1 = [], list2 = []
Output[]
WhyBoth lists have no nodes, so the merged list is empty too.
Example 3
Inputlist1 = [], list2 = [0]
Output[0]
WhyOne list is empty, so the answer is just the other list unchanged.

Asked At

6 companies
CompanyDifficulty
AmazonEasyView all Amazon questions →
MicrosoftEasyView all Microsoft questions →
AdobeEasyView all Adobe questions →
OracleEasyView all Oracle questions →
RipplingEasyView all Rippling questions →
BloombergEasyView all Bloomberg questions →

How to Think About It

1

Use a dummy head node to avoid special-casing the first node. The dummy's next pointer always points to the result. Return dummy.next at the end.

2

Compare the heads of both lists. The smaller node goes next in the result. Advance that list's pointer. Repeat until one list is exhausted.

3

When one list runs out, the other list still has nodes. Attach the remainder directly — it's already sorted.

4

Recursive approach: if l1.val <= l2.val, l1.next = merge(l1.next, l2). Else l2.next = merge(l1, l2.next). Elegant but O(m+n) stack space.

Optimal Approach

Step 1: Create dummy head and tail pointer.
Step 2: While both lists have nodes:

  • Compare l1.val and l2.val
  • Attach the smaller node to tail
  • Advance that list's pointer
  • Advance tail
    Step 3: Attach the remainder (l1 or l2, whichever is non-null).
    Step 4: Return dummy.next.

The dummy head eliminates the "is this the first node?" check. Every node is appended the same way.

Time: O(m + n). Space: O(1) iterative, O(m + n) recursive.

Dummy head plus tail pointer

before124nulll1l1 points at 1; l2 points at 1. Compare the two front values.result so far1123nulltailEach step we attach the smaller front node and move that list forward.finish112344nullWhen one list runs out, we attach the rest of the other list in one go.while l1 and l2: attach smaller front nodetail.next = l1 or l2return dummy.next
A dummy node removes the special case for the first node; tail always points at the last node we placed.
ComplexityTime O(m + n)Space O(1)We touch each node once, and the iterative version only keeps a few pointers, so no extra memory grows with the input.

What Trips People Up in Real Interviews

1

Creating a new list instead of modifying the existing ones. The problem says you can modify the input lists. Use the existing nodes to save space.

2

Forgetting to append the remaining list. After the main loop, one list might still have elements. Append the rest of the non-empty list.

3

Not handling empty lists. If one list is null, return the other. If both are null, return null.

4

Confusing "merge" with "concatenate." Merging interleaves elements in sorted order, not appends one list after the other.

5

Not handling the case where both lists have equal values. When l1.val == l2.val, either choice works, but you must advance one pointer — don't skip both or advance neither.

Solution Code

O(m + n) time
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Merge Two Sorted Lists problem?

Merge two sorted linked lists into one sorted list. This is a foundational linked list problem that appears frequently as a warm-up or follow-up question in FAANG interviews.

How do you solve Merge Two Sorted Lists?

The optimal approach runs in O(m + n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Merge Two Sorted Lists?

Merge Two Sorted Lists is asked at Amazon, Microsoft, Adobe, Oracle, Rippling, Bloomberg. It is a easy difficulty problem.

What are common mistakes on Merge Two Sorted Lists?
  • Creating a new list instead of modifying the existing ones. The problem says you can modify the input lists. Use the existing nodes to save space.
  • Forgetting to append the remaining list. After the main loop, one list might still have elements. Append the rest of the non-empty list.
  • Not handling empty lists. If one list is `null`, return the other. If both are `null`, return `null`.
  • Confusing "merge" with "concatenate." Merging interleaves elements in sorted order, not appends one list after the other.
  • Not handling the case where both lists have equal values. When `l1.val == l2.val`, either choice works, but you must advance one pointer — don't skip both or advance neither.