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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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.
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.