⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#21) before relying on it.

Merge Two Sorted Lists

An interactive visualization of the merge technique using a dummy head node. Watch how two sorted linked lists are merged into one sorted list by comparing nodes and linking them together.

Linked List LeetCode 21 ↗ Easy

The Problem

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.

Interactive Visualization

List 1 (comma-separated)

List 2 (comma-separated)

Preset

Speed:

Linked Lists Visualization

Code

fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {    val dummy = ListNode(0)    var current = dummy    var l1 = list1    var l2 = list2    while (l1 != null && l2 != null) {        if (l1.`val` <= l2.`val`) {            current.next = l1            l1 = l1.next        } else {            current.next = l2            l2 = l2.next        }        current = current.next!!    }    current.next = l1 ?: l2    return dummy.next}

def mergeTwoLists(list1, list2):    dummy = ListNode(0)    current = dummy    while list1 and list2:        if list1.val <= list2.val:            current.next = list1            list1 = list1.next        else:            current.next = list2            list2 = list2.next        current = current.next    current.next = list1 or list2    return dummy.next

Status

Press Step or Play to begin.

How It Works

Key Insight

The dummy head technique eliminates the need for special-case logic when building a new linked list. By creating a placeholder node at the start, we always have a valid current pointer to attach the next node to, and the real head of the merged list is simply dummy.next.

The Algorithm

Initialize: Create a dummy node and set current = dummy. This dummy node acts as a placeholder head for the merged list.
Compare and link: While both lists have remaining nodes, compare the front nodes. Attach the smaller one to current.next and advance that list's pointer.
Advance current: After each attachment, move current to current.next so the next node can be appended.
Append remainder: When one list is exhausted, attach the remaining nodes of the other list directly to current.next.
Return: dummy.next is the head of the merged sorted list (skipping the dummy placeholder).

Complexity

Time O(n + m)

Space O(1)

We visit each node exactly once across both lists, giving O(n + m) time where n and m are the lengths of the two lists. We only use a constant number of pointers — no extra data structures needed.