Merge Two Sorted Lists

Easy Problem 49 of 151 Java and Python

Problem

You are given the heads of two sorted linked lists, list1 and list2. Merge them into one sorted list made by splicing together the nodes of the two lists, 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 ≤ number of nodes in each list ≤ 50
Both lists are sorted in non-decreasing order.

Explanation

At each step the smallest remaining node is the head of one of the two lists. Take it, attach it to the result, and advance that list.

A dummy node in front of the result means you never have to special-case the first node.

Approach 1 · Naive

Collect, sort, rebuild

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

Put every value into an array, sort it, and build a new list. It ignores that the inputs are already sorted.

Collect the values of both lists.
Sort and build a new list from them.

Java

import java.util.*;

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        List<Integer> values = new ArrayList<>();
        for (ListNode n = list1; n != null; n = n.next) {
            values.add(n.val);
        }
        for (ListNode n = list2; n != null; n = n.next) {
            values.add(n.val);
        }
        Collections.sort(values);
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Python

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        values = []
        for node in (list1, list2):
            while node:
                values.append(node.val)
                node = node.next
        dummy = tail = ListNode()
        for v in sorted(values):
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

Approach 2 · Optimal

Splice with a dummy head

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

Compare the two heads, attach the smaller to tail, advance. When one list runs out, attach the rest of the other.

Create dummy and tail = dummy.
While both lists have nodes: attach the smaller head to tail.next, advance that list and tail.
Attach whichever list is left. Return dummy.next.

Java

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

Python

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode()
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next, list1 = list1, list1.next
            else:
                tail.next, list2 = list2, list2.next
            tail = tail.next
        tail.next = list1 or list2
        return dummy.next

Complexity compared

Approach	Time	Space
Naive Collect, sort, rebuild	O((m + n) log(m + n))	O(m + n)
Optimal Splice with a dummy head	O(m + n)	O(1)

Key takeaways

Use a dummy head whenever the first node of the result is not known in advance.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem