ToolMight LogoToolMight
EasyLinked ListPattern: Dummy HeadPattern: Pointer SplicingPattern: Two Pointers

Merge Two Sorted Lists

Splice together nodes of two sorted linked lists into a single sorted list. The canonical problem for learning pointer reassignment and the dummy head technique.

Problem Statement

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.

Examples & Constraints

Example 1
Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Explanation: Comparing node values from both heads yields a sorted merged sequence.
Example 2
Input: list1 = [], list2 = [0]
Output: [0]
Explanation: One list is empty, so the merged output is simply the non-empty list.
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.

Iterative Splicing with Dummy Head

Optimal Approach
Time:O(n + m)
Space:O(1)

Use a dummy head node and a current pointer to stitch existing nodes together in O(1) auxiliary space without allocating new nodes.

Time ComplexityO(n + m)

Every node across both input lists of lengths N and M is visited and linked exactly once.

Space ComplexityO(1)

No new nodes are created. Only a single dummy node and pointer references are used.

Underlying algorithmic logic

The Dummy Head Technique: Eliminating Edge Cases

In linked list manipulation, the most common source of null pointer exceptions is deciding which node becomes the head of the merged list.

By initializing a sentinel dummy node (dummy) and a tracking pointer (tail = dummy):

  1. We never have to write special branches for the first node insertion.
  2. While both list1 and list2 are non-null:
  • If list1.val <= list2.val, wire tail.next = list1 and advance list1 = list1.next.
  • Else, wire tail.next = list2 and advance list2 = list2.next.
  • Advance tail = tail.next.
  1. When one list runs out of nodes, attach the remaining tail directly: tail.next = (list1 != null) ? list1 : list2.
  2. Return dummy.next as the true head of the merged list.

In-Place Pointer Rewiring

Notice that we do not allocate any new list nodes! We only change the next pointers of the existing input nodes. This guarantees O(1) auxiliary memory.

Step-by-step execution walkthrough

1
Initialize Dummy

Create dummy node (-1). tail points to dummy. list1 at 1, list2 at 1.

tail -> dummy, list1: 1->2->4, list2: 1->3->4
2
First Node Match

list1.val (1) <= list2.val (1). tail.next points to list1 (1). Advance list1.

merged: dummy -> 1 (from list1)
3
Next Comparison

list2.val (1) < list1.val (2). tail.next points to list2 (1). Advance list2.

merged: dummy -> 1 -> 1
4
Remaining Attach

Continue splicing until list1 is exhausted. Wire remaining list2 directly.

Final: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Advantages
  • •Optimal O(1) auxiliary space
  • •Clean logic without edge cases thanks to dummy head
Trade-offs
  • •Mutates original list nodes (standard competitive programming behavior)

Code Implementations

Copy & paste production-ready solutions for Iterative Splicing with Dummy Head in your language of choice

File: solution.py
Python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def merge_two_lists(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    dummy = ListNode(-1)
    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
def to_list(head: ListNode | None) -> list[int]:
    res = []
    curr = head
    while curr:
        res.append(curr.val)
        curr = curr.next
    return res
if __name__ == "__main__":
    l1 = ListNode(1, ListNode(2, ListNode(4)))
    l2 = ListNode(1, ListNode(3, ListNode(4)))
    merged = merge_two_lists(l1, l2)
    print("Merged list:", to_list(merged))
Interactive visualizer available

Understand Singly Linked List Visually

Interact with linear chain node arrays, traversal, head/tail adjustments, and index operations. Test live edge cases and watch memory state transitions step-by-step.

Launch Singly Linked List Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyLinked List
Visualizer

Reverse Linked List

Reverse the directional arrows of a singly linked list in-place. The classic test of reference manipulation and memory pointer management.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyLinked List
Visualizer

Linked List Cycle

Determine if a linked list contains a cycle using Floyd's Tortoise and Hare algorithm. The foundational problem for understanding two-speed pointer convergence in finite loops.

1 approach(O(n))
Learn logic