Compile Ready
Module 2 · Basic Operations

Merge Two Sorted Lists

EasyProblem 3 of 17 9 min read ~18 min to solve LeetCode
Linked ListMergeDummy NodeRecursionSorting
Asked atMicrosoftAmazonGoogleMetaOracle

Problem Statement

You are given the heads of two sorted linked lists list1 and list2. Merge them into one sorted linked list by splicing together existing nodes, and return the head of the merged list.

Input

Two head pointers, list1 and list2, each representing a sorted singly linked list.

Output

The head pointer of one sorted linked list containing all nodes from both inputs.

Constraints

  • •0 <= number of nodes in each list <= 50
  • •-100 <= Node.val <= 100
  • •Both input lists are sorted in non-decreasing order

Examples

Example 1

Input: 
list1 = **1 -> 2 -> 4 -> null**, list2 = **1 -> 3 -> 4 -> null**
Output: **1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null**
Explanation: Repeatedly taking the smaller front node preserves sorted order and includes both **1** values and both **4** values.

Example 2

Input: 
list1 = **null**, list2 = **0 -> null**
Output: **0 -> null**
Explanation: When one list is empty, the merged list is simply the other list.

Learning Objectives

  • Use a dummy head to remove special handling for the first merged node.
  • Maintain a **tail** pointer that always marks where the next chosen node should be attached.
  • Explain why attaching the remaining suffix is safe once one list is exhausted.
  • Compare iterative splicing with the recursive merge formulation.

Intuition

Pattern Recognition

The signal is merge two sorted linked lists or any task where two sorted streams must be combined while preserving order. Since the smallest remaining value must be at the head of one of the lists, each step compares only list1.val and list2.val.

The pointer trap is mishandling the first node of the result. Without a dummy node, you need separate logic for an empty merged list versus later appends. A dummy head gives tail a stable starting point. You attach the smaller node to tail.next, advance that source list, and move tail forward. Another trap is creating unnecessary new nodes; the expected linked-list solution splices existing nodes.

Common mistakes

  • ×Writing special-case code for the first node instead of using a dummy head.
  • ×Advancing **tail** before attaching **tail.next**, which can lose the merged chain.
  • ×Forgetting to attach the non-empty remainder after the main comparison loop.
  • ×Allocating new nodes when the problem expects existing nodes to be rewired.

Algorithm Explanation

Key idea

Keep a dummy node before the merged list and a tail pointer at the last merged node. The invariant is that dummy.next -> ... -> tail is sorted, and list1 plus list2 contain the remaining unmerged nodes. Append the smaller front node and advance only the list it came from.

Pointer walkthrough

For list1 = 1 -> 2 -> 4 -> null and list2 = 1 -> 3 -> 4 -> null, begin with dummy -> null and tail = dummy. Compare the two heads, both 1. Choose the first list on ties, so dummy -> 1 and list1 moves to 2. Now compare 2 and 1. Attach the 1 from list2, so the merged prefix is dummy -> 1 -> 1 and list2 moves to 3.

Next compare 2 and 3, attach 2 and move list1 to 4. Compare 4 and 3, attach 3 and move list2 to 4. Compare 4 and 4, attach the 4 from list1. Now list1 is empty, so attach the remaining 4 -> null from list2 directly after tail. Return dummy.next, which skips the placeholder.

Algorithm

  1. Create dummy and set tail = dummy.
  2. While both list1 and list2 are not null, compare their values.
  3. Attach the smaller head node to tail.next and advance that source list.
  4. Move tail to tail.next after each attachment.
  5. When one list becomes empty, set tail.next to the other list.
  6. Return dummy.next.

Solutions

Solution 1: Dummy head with tail splicing

When to prefer this:

Use this as the default interview solution. It is iterative, stable on equal values when you choose list1 first, and uses constant extra space.

Build the merged list behind a dummy head. At each step, splice the smaller current node after tail, advance that input pointer, then advance tail. After the loop, attach the remaining suffix in one operation.

Step-by-step

  1. Create a dummy node and set tail to it.
  2. While both input lists have nodes, compare list1.val and list2.val.
  3. Link tail.next to the smaller node.
  4. Advance the list pointer that supplied the node.
  5. Advance tail to the node just attached.
  6. Attach the remaining non-empty list and return dummy.next.
Time

O(m + n)

Space

O(1)

Every node is appended once, and the algorithm stores only a dummy and a tail pointer.

Java implementation

Loading…

Solution 2: Recursive sorted merge

When to prefer this:

Use this when the interviewer wants the shortest recursive expression of the merge relation. Avoid it for extremely long lists because recursion uses stack space.

Choose the smaller head as the head of the merged result, then recursively merge its next pointer with the other list. The base case returns the non-empty list when the other one is exhausted.

Step-by-step

  1. If list1 is null, return list2.
  2. If list2 is null, return list1.
  3. If list1.val <= list2.val, set list1.next to the merge of list1.next and list2, then return list1.
  4. Otherwise set list2.next to the merge of list1 and list2.next, then return list2.
Time

O(m + n)

Space

O(m + n)

Each node participates in one recursive decision, and the call stack can grow to the merged length.

Java implementation

Loading…

Dry Run

Sample input

list1 = 1 -> 2 -> 4 -> null, list2 = 1 -> 3 -> 4 -> null. Track the merged prefix after each splice.

steplist1 headlist2 headnode attachedmerged prefix
start11none**dummy -> null**
1111 from list1**dummy -> 1**
2211 from list2**dummy -> 1 -> 1**
3232 from list1**dummy -> 1 -> 1 -> 2**
4433 from list2**dummy -> 1 -> 1 -> 2 -> 3**
5444 from list1**dummy -> 1 -> 1 -> 2 -> 3 -> 4**
attach remaindernull4remaining list2**dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null**

The dummy node is not part of the answer. Returning dummy.next yields 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null.

Interview Tips

Emphasise that tail always points to the last node in the merged prefix. Once one input list is empty, the other list is already sorted, so there is no reason to keep comparing or copying nodes. If asked about stability, choosing list1 when values are equal preserves the relative order of equal nodes from the first list before equal nodes from the second.

Likely follow-ups

  • How would you merge **k** sorted linked lists?
  • How would you sort one unsorted linked list using merge sort?
  • What changes if the merged list must allocate brand-new nodes instead of reusing existing ones?
  • How would you merge lists in descending order?

Similar Problems

Merge k Sorted Lists
HardGeneralises the two-list merge using a heap or divide and conquer.
Sort List
MediumUses middle splitting and the same merge primitive.
Partition List
MediumAlso builds linked-list chains with dummy heads and tails.
Add Two Numbers
MediumAnother two-list traversal that appends nodes behind a moving tail.

Key Takeaways

  • A dummy head turns first-node insertion into the same operation as every later insertion.
  • The **tail** pointer marks the end of the merged prefix and moves after each splice.
  • After one list ends, the remaining suffix can be attached directly.
  • Merging sorted lists is the core primitive behind linked-list merge sort and k-way merge.
Reusable template: Dummy-tail merge: keep a placeholder before the answer, repeatedly splice the smaller front node after tail, then append the leftover sorted suffix.