Start practising

Merge Two Sorted Lists

Easy Linked List Dummy Node Pattern Original on LeetCode

Merge Two Sorted Lists is a easy linked list problem solved with the dummy node pattern pattern. The best approach, optimal (iterative with a dummy node), runs in O(m + n) time and O(1) space. Below are 2 approaches in Java, from recursive up.

Problem

Merge two sorted linked lists into one sorted list by splicing their nodes together, and return its head.

Examples

Example 1

Input
list1 = [1, 4, 6], list2 = [2, 4, 9]
Output
[1, 2, 4, 4, 6, 9]

Example 2

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

Constraints

  • Each list has 0 to 50 nodes, sorted in non-decreasing order.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
RecursiveO(m + n)O(m + n)
Optimal (iterative with a dummy node)O(m + n)O(1)

1Recursive

TimeO(m + n)
SpaceO(m + n)Recursion depth equals the total length.

The smaller head goes first; its next is the merge of the rest.

  1. If either list is empty, return the other.
  2. If l1.val <= l2.val: l1.next = merge(l1.next, l2); return l1. Else symmetric.
Java
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

2Optimal (iterative with a dummy node)

TimeO(m + n)
SpaceO(1)

Keep a tail pointer starting at a dummy node. Attach the smaller of the two heads each step, then attach whatever remains.

  1. tail = dummy.
  2. While both are non-empty, attach the smaller head and advance it.
  3. tail.next = the non-empty remainder; return dummy.next.
Java
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(), tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
            else { tail.next = l2; l2 = l2.next; }
            tail = tail.next;
        }
        tail.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

Edge cases to test

  • One or both lists empty
  • Equal values in both lists

Hints

Hint 1

A dummy head node removes the question of which list supplies the first node.

FAQ

What is the best time complexity for Merge Two Sorted Lists?

Optimal (iterative with a dummy node) runs in O(m + n) time and O(1) extra space.

Which pattern does Merge Two Sorted Lists use?

It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Remove Linked List Elements, Delete Nodes From Linked List Present in Array, Rotate List.

Is there a brute force solution for Merge Two Sorted Lists?

Yes. Recursive takes O(m + n) time and O(m + n) space. The smaller head goes first; its next is the merge of the rest.

Which edge cases should I test for Merge Two Sorted Lists?

One or both lists empty; Equal values in both lists.