Merge Two Sorted Lists

Problem

https://leetcode.com/problems/merge-two-sorted-lists/

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• The number of nodes in both lists is in the range [0, 50].

• -100 <= Node.val <= 100

• Both list1 and list2 are sorted in non-decreasing order.

Pattern

Linked List, Recursion

Approaches

Iterative

Explanation

The general idea is to merge the lists by selecting the smaller node from list1 and list2. We then set the next field of the current node to the minimum node, advancing the list1/list2 and node pointers. We can apply 2 tricks to simplify the code at the beginning and the end of the merge process.

1. Rather than have a special case for the head of the merged list, start with a dummy node. New nodes are added after the dummy node, and we return dummy.next as the head of the merged list.

2. Once we reach the end of one of the lists, we can simply point the next field of the current node to the other list, since it is already sorted.

Code

from __future__ import annotations


class ListNode:
    """Node in a linked list."""

    def __init__(self, val: int, next: ListNode | None = None):
        self.val = val
        self.next = next

    def __str__(self) -> str:
        suffix = " -> " + str(self.next) if self.next else ""
        return str(self.val) + suffix

    @classmethod
    def from_list(cls, list: list[int]) -> ListNode | None:
        head = None
        for el in list:
            if head is None:
                head = ListNode(el)
                node = head
            else:
                node.next = ListNode(el)
                node = node.next
        return head


def merge_2_lists(
    list1: ListNode | None, list2: ListNode | None
) -> ListNode | None:
    """Merge two sorted linked lists."""
    dummy = node = ListNode(0)
    while list1 and list2:
        if list1.val < list2.val:
            node.next = list1
            list1 = list1.next
        else:
            node.next = list2
            list2 = list2.next

        node = node.next

    node.next = list1 or list2

    return dummy.next

Test

>>> from merge_two_sorted_lists__iterative import ListNode, merge_2_lists
>>> head1 = ListNode.from_list([1, 2, 4])
>>> head2 = ListNode.from_list([1, 3, 4])
>>> head = merge_2_lists(head1, head2)
>>> print(head)
1 -> 1 -> 2 -> 3 -> 4 -> 4

Complexity

\(m\) is the length of the first input list and \(n\) is the length of the second input list

Measure	Complexity	Notes
Time	\(O(m + n)\)	go through both lists
Auxiliary Space	\(O(1)\)

class merge_two_sorted_lists__iterative.ListNode(val: int, next: ListNode | None = None)

Bases: object

Node in a linked list.

classmethod from_list(list: list[int]) → ListNode | None

merge_two_sorted_lists__iterative.merge_2_lists(list1: ListNode | None, list2: ListNode | None) → ListNode | None

Merge two sorted linked lists.