Command Palette

Search for a command to run...

Hectal
Problem 8.4 · Linked ListsEasy

Merge Two Sorted Lists

PatternDummy Head and Merging

What it teaches: Build a new list behind a dummy head by always taking the smaller front node.

Practise it on judges as “Merge Two Sorted Lists”.

The problem

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

Example 1

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]

Example 2

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

Constraints

  • 0 ≤ nodes in each list ≤ 50
  • Both sorted non-decreasing

Pattern clues in the wording

  • → Two sorted sequences combined in order
  • → Building a new list → dummy head

These clues point to Dummy Head and Merging: Start with a fake node before the real head so building, merging and deleting never need special cases for the first node.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), tail = dummy;
        return dummy.next;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
a = [1,2,4]
b = [1,3,4]
[1,1,2,3,4,4]
2
a = []
b = []
[]
3
a = []
b = [0]
[0]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: dummy head and tail · O(n + m)
1

Optimal: dummy head and tail

Time O(n + m) Space O(1)

tail starts at a dummy. While both lists have nodes, attach the smaller front node to tail and advance. Then attach the leftover list.

▶ Dry run: Taking the smaller front each timelist1 = [1, 2, 4], list2 = [1, 3, 4]
1
↑a
2
4
null

list2(list)

134

merged(list)

empty

Step 1/4Fronts: 1 and 1. Equal: take from list1 (keeps it stable).

Approach 1
class Solution {
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;
        return dummy.next;
    }
}

Verdict: Each node is attached once; no new nodes created.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One or both lists empty
  • All of one list smaller than the other
  • Equal values

Mistakes people make

  • Forgetting to attach the leftover list.
  • Creating new nodes instead of splicing (works, but uses O(n + m) memory).

Interview

Follow-up questions

How would you sort a linked list in O(n log n)?