Merge Two Sorted Lists

PracticeNeetCode ↗LeetCode ↗

Given the heads of two sorted linked lists, merge them into a single sorted list and return its head.

Example

Key Pointers

• A dummy head node avoids special-casing "what's the first node of the result".
• At each step, attach whichever current node is smaller, then advance only that list's pointer.
• Once one list is exhausted, the rest of the other list is already sorted — attach it directly, no more comparisons needed.

Step-by-Step Analysis

1. Create a dummy node and a tail pointer starting at dummy.
2. While both lists have nodes: compare their values, attach the smaller to tail.next, advance that list's pointer and tail.
3. When one list runs out, attach whatever remains of the other list to tail.next.
4. Return dummy.next as the merged list's head.

Complexity

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

Code

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

def mergeTwoLists(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 if list1 else list2
    return dummy.next

Code Explanation

How the solution above works, piece by piece.

1. dummy is a placeholder node before the real head, so the first node doesn't need a special case. tail is the end of the merged list so far.
2. While both lists have nodes, compare their fronts and link the smaller one after tail.
3. Advance the list you took from, then move tail forward.
4. When one list is empty, the other is already sorted: attach it whole with tail.next = list1 if list1 else list2.
5. Return dummy.next. No new nodes are created, only pointers are relinked: O(m + n) time, O(1) space.

Visual Walkthrough

Running it on list1 = [1, 2, 4], list2 = [1, 3, 4]:

Video Explanation

NeetCode — LeetCode 21