Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    EasyLinked List

    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.
    View original on LeetCode ↗

    Both lists are already sorted, so the smallest remaining value is always at the front of one of them. Repeatedly pick the smaller of the two front nodes and splice it onto the result — no new nodes need to be allocated.

    Recursive

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

    At each step, compare the two heads and let the smaller one absorb the recursively-merged rest of the lists. The recursion depth equals the total number of nodes, so the call stack itself costs O(n + m) space even though no extra list nodes are created.

    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
    

    class Solution:
        def mergeTwoLists(self, list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
            if not list1:
                return list2
            if not list2:
                return list1
            if list1.val <= list2.val:
                list1.next = self.mergeTwoLists(list1.next, list2)
                return list1
            else:
                list2.next = self.mergeTwoLists(list1, list2.next)
                return list2

    Clean and easy to prove correct by induction, but the recursion stack grows with the combined length of both lists — an iterative version avoids that entirely.

    Iterative With Dummy Head

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

    Walk both lists with a tail pointer that always points at the last node placed into the result. A dummy sentinel node avoids special-casing “is this the first node?” — we just return dummy.next at the end. Once one list runs out, the rest of the other list is already sorted, so it can be attached directly.

    class Solution:
        def mergeTwoLists(self, list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
            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 or list2   # attach whichever list still has nodes
            return dummy.next

    Watch the two source rows get consumed left to right while p1, p2 and tail advance — the amber pair is being compared, the ringed node is the one just spliced, and the final step relinks the remaining sorted tail in one shot.

    list1

    124
    ▲ p1

    list2

    134
    ▲ p2

    merged result

    1 / 8
    comparingcurrentresultseen

    Start: p1 and p2 sit on the two heads (both 1). Each round compares the two heads and splices the smaller node onto tail.

    Why it’s correct: at every step the smaller of the two current heads is guaranteed to be the smallest value not yet placed in the result, since both source lists are sorted — so the output is built in non-decreasing order by construction. Complexity: each node from both lists is visited and attached exactly once → O(n + m) time, O(1) extra space (we reuse the existing nodes, only the dummy sentinel is new) — optimal, since every node must be examined at least once.

    More Linked List practice