Merge Two Sorted Lists — InterviewPrepKit

Solving tips

This is the merge step of merge sort: the next node is always the smaller of the two current heads, one comparison per output node.
Use a dummy head so you always append to tail.next and return dummy.next, collapsing the empty-result and first-node special cases.
After the loop, attach the remaining tail with 'tail.next = list1 if list1 else list2' or the leftover longer list silently disappears.
Splice existing nodes (don't allocate new ones); O(n + m) time, O(1) space iteratively, and use '<=' to keep the merge stable.

Problem

You are given the heads of two singly linked lists, list1 and list2, each already sorted in non-decreasing order. Splice the two lists together into one sorted list — reuse the existing nodes rather than allocating new ones — and return the head of the merged list.

Examples

Input: list1 = 1 -> 2 -> 4, list2 = 1 -> 3 -> 4 → Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 Interleave the nodes so the result stays sorted.
Input: list1 = (empty), list2 = (empty) → Output: (empty) Nothing to merge.
Input: list1 = (empty), list2 = 0 → Output: 0 One empty list means the answer is just the other list.

Constraints

Each list has [0, 50] nodes.
-100 <= Node.val <= 100
Both lists are sorted in non-decreasing order.

Think about it first

Hint 1

Both lists are already sorted. At any moment, which node must come next in the merged output? You only ever need to compare two nodes.

Hint 2

Building a list forward is awkward when you don't yet have a first node. A throwaway "dummy" head node lets you always append to tail.next and return dummy.next at the end.

Hint 3

Repeatedly: compare the two front nodes, link the smaller one onto the tail of the result, and advance that list. When one list runs out, attach the entire remainder of the other — it's already sorted.

TL;DR

Two-pointer splice with a dummy head — O(n + m) time, O(1) space (iterative).

Approach 1 — Brute force: collect, sort, rebuild

Ignore that the inputs are sorted: dump every value into a Python list, sort it, and build a fresh linked list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional


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

Complexity: O((n+m) log(n+m)) time, O(n+m) space.

With 50-node lists nothing “kills” this — what kills it in an interview is that it throws away the sortedness, allocates all-new nodes (the problem says to splice the existing ones), and pays a needless log factor.

Approach 2 — Iterative two-pointer merge with a dummy head

The insight: the next node of the answer is always the smaller of the two current front nodes — this is exactly the merge step of merge sort (the classical divide-and-conquer sorting algorithm whose combine phase merges two sorted runs in linear time). A dummy head removes the “is this the first node?” special case.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional


class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy = ListNode()
        tail = dummy
        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 if list1 else list2
        return dummy.next

Walkthrough on list1 = 1 -> 2 -> 4, list2 = 1 -> 3 -> 4:

compare	take	result so far
1 vs 1	list1’s 1 (ties go left)	1
2 vs 1	list2’s 1	1 -> 1
2 vs 3	2	1 -> 1 -> 2
4 vs 3	3	1 -> 1 -> 2 -> 3
4 vs 4	list1’s 4	1 -> 1 -> 2 -> 3 -> 4
list1 empty	attach rest of list2	1 -> 1 -> 2 -> 3 -> 4 -> 4

Complexity: O(n + m) time, O(1) extra space — nodes are relinked in place.

Approach 3 — Recursive merge

The insight: the merge has a clean self-similar definition — the merged list is the smaller head, followed by the merge of everything that remains. The base case is one list being empty.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional


class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2

Walkthrough on the same example: the first call picks list1’s 1 and recurses on (2->4, 1->3->4); that call picks 1 and recurses on (2->4, 3->4); then 2, then 3, then 4, then list1 is empty so 4 (the rest of list2) is returned and the stack unwinds, wiring 1 -> 1 -> 2 -> 3 -> 4 -> 4.

Complexity: O(n + m) time, O(n + m) space for the call stack — fine at 100 total nodes, but the iterative version is the safe default on long lists (Python’s default recursion limit is 1000).

Common pitfalls

Forgetting tail.next = list1 if list1 else list2 after the loop — the leftover tail of the longer list silently disappears.
Returning dummy instead of dummy.next, adding a phantom 0 node to the front.
Building the result with new ListNode(...) copies when the problem asks you to splice the given nodes.
Using < instead of <= doesn’t break correctness here, but <= keeps the merge stable (equal elements keep their original relative order), which interviewers sometimes probe.

Pattern takeaway

When two inputs are each sorted, the answer’s next element is always one of two candidates — a single comparison per output node gives a linear merge. And any time you build a linked list front-to-back, start with a dummy head: it collapses the empty-result and first-node special cases into the general one.