LeetCode 21 - Merge Two Sorted Lists

This problem asks us to merge two already sorted singly linked lists into one new sorted linked list. The important detail is that we are not creating entirely new nodes for the merged result. Instead, we reuse the existing nodes by reconnecting their next pointers.

leetcodeeasylinked-listrecursion

LeetCode Problem 21

Difficulty: 🟢 Easy
Topics: Linked List, Recursion

Solution

Problem Understanding

This problem asks us to merge two already sorted singly linked lists into one new sorted linked list. The important detail is that we are not creating entirely new nodes for the merged result. Instead, we reuse the existing nodes by reconnecting their next pointers.

Each input list is sorted in non-decreasing order. That means values can repeat, and every node's value is less than or equal to the value of the nodes after it.

For example:

  • list1 = [1,2,4]
  • list2 = [1,3,4]

Both lists are individually sorted. The merged result must also remain sorted:

  • [1,1,2,3,4,4]

The input represents the heads of two singly linked lists. Each node contains:

  • A value, val
  • A pointer to the next node, next

The output should be the head node of the merged linked list.

The constraints are very small, at most 50 nodes total across both lists. Because of this, almost any reasonable algorithm will run fast enough. Still, this problem is important because it teaches a fundamental linked list pattern used in many harder problems, especially merge sort on linked lists.

Several edge cases matter immediately:

  • One or both lists may be empty
  • Both lists may contain duplicate values
  • All nodes from one list may come before the other
  • The lists may have different lengths
  • Values may be negative

The problem guarantees that both input lists are already sorted. That guarantee is what allows an efficient linear-time merge.

Approaches

Brute Force Approach

A straightforward way to solve the problem is:

  1. Traverse both linked lists
  2. Copy all values into an array
  3. Sort the array
  4. Create a brand new linked list from the sorted values

This works because sorting all values guarantees the final list is ordered correctly.

For example:

  • Extract values: [1,2,4,1,3,4]
  • Sort: [1,1,2,3,4,4]
  • Build new linked list

Although correct, this approach ignores an important property of the input: both lists are already sorted. Re-sorting the data does unnecessary work.

It also uses extra memory because we store all values in an array and create entirely new nodes.

Optimal Approach

The key observation is that both lists are already sorted.

This means the smallest remaining element must always be at the front of one of the two lists. We can repeatedly compare the current nodes of both lists and attach the smaller one to the merged result.

This is the same idea used in the merge step of merge sort.

We maintain:

  • A pointer into list1
  • A pointer into list2
  • A tail pointer for the merged list

At each step:

  • Choose the smaller current node
  • Attach it to the merged list
  • Advance the corresponding pointer

Because every node is processed exactly once, the algorithm runs in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O((n + m) log(n + m)) O(n + m) Extract values, sort them, rebuild list
Optimal O(n + m) O(1) Merge lists directly using pointer manipulation

Here, n and m are the lengths of the two linked lists.

Algorithm Walkthrough

Iterative Merge Algorithm

  1. Create a dummy node that acts as the temporary start of the merged list.

The dummy node simplifies edge cases because we never need special logic for the first inserted node. 2. Create a tail pointer initially pointing to the dummy node.

The tail pointer always represents the last node in the merged list. 3. While both list1 and list2 are not empty:

  • Compare list1.val and list2.val
  • Attach the smaller node to tail.next
  • Move the corresponding list pointer forward
  • Advance tail

This guarantees the merged list remains sorted at every step. 4. After the loop, one list may still contain remaining nodes.

Since the remaining nodes are already sorted, we can attach the rest directly without further comparisons. 5. Return dummy.next.

We skip the dummy node itself because it was only used to simplify construction.

Why it works

At every step, the algorithm chooses the smallest available node from the fronts of the two sorted lists. Since all remaining nodes behind that chosen node are greater than or equal to it, attaching the smaller front node preserves sorted order.

The invariant is:

  • The merged list built so far is always sorted.
  • All nodes not yet processed remain sorted in their original lists.

Because the algorithm processes every node exactly once while maintaining this invariant, the final merged list is correctly sorted.

Python Solution

# 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

        if list1:
            tail.next = list1
        else:
            tail.next = list2

        return dummy.next

The implementation starts by creating a dummy node. This node avoids special handling for the first insertion into the merged list.

The tail pointer always tracks the last node in the merged result. Initially, both tail and dummy point to the same node.

The while loop continues as long as both lists still contain nodes. Inside the loop, we compare the current node values:

  • If list1.val is smaller or equal, we attach that node
  • Otherwise, we attach the node from list2

After attaching a node, we move the corresponding list pointer forward because that node has now been consumed.

We also move tail forward so it always stays at the end of the merged list.

When the loop finishes, one list is exhausted. Since the other list is already sorted, we can attach the remaining portion directly.

Finally, we return dummy.next because the dummy node itself is not part of the answer.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy

	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			tail.Next = list1
			list1 = list1.Next
		} else {
			tail.Next = list2
			list2 = list2.Next
		}

		tail = tail.Next
	}

	if list1 != nil {
		tail.Next = list1
	} else {
		tail.Next = list2
	}

	return dummy.Next
}

The Go implementation follows the exact same logic as the Python version.

The main language-specific difference is handling nil pointers instead of Python's None.

Go uses explicit pointer syntax:

  • &ListNode{} creates a new node
  • tail.Next accesses the next pointer

No integer overflow concerns exist here because node values stay within very small bounds.

Worked Examples

Example 1

Input:

list1 = [1,2,4]
list2 = [1,3,4]

Initial state:

Step list1 list2 Chosen Node Merged List
Start 1->2->4 1->3->4 None []

Compare first nodes:

  • 1 <= 1, choose node from list1
Step list1 list2 Chosen Node Merged List
1 2->4 1->3->4 1 [1]

Compare again:

  • 2 > 1, choose node from list2
Step list1 list2 Chosen Node Merged List
2 2->4 3->4 1 [1,1]

Next comparison:

  • 2 <= 3, choose 2
Step list1 list2 Chosen Node Merged List
3 4 3->4 2 [1,1,2]

Next comparison:

  • 4 > 3, choose 3
Step list1 list2 Chosen Node Merged List
4 4 4 3 [1,1,2,3]

Next comparison:

  • 4 <= 4, choose node from list1
Step list1 list2 Chosen Node Merged List
5 None 4 4 [1,1,2,3,4]

list1 is exhausted, append remaining nodes from list2.

Final result:

[1,1,2,3,4,4]

Example 2

Input:

list1 = []
list2 = []

Both lists are empty immediately.

The loop never runs.

Result:

[]

Example 3

Input:

list1 = []
list2 = [0]

Since list1 is empty, the loop never runs.

We directly attach the remaining nodes from list2.

Result:

[0]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each node is visited exactly once
Space O(1) Only a few pointers are used

The algorithm processes each node one time during the merge. No nested traversal occurs, so the runtime is linear in the total number of nodes.

The space complexity is constant because the algorithm reuses existing nodes instead of allocating additional data structures proportional to input size.

Test Cases

# Helper utilities for testing

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

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def linked_list_to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

solution = Solution()

# Example 1
head = solution.mergeTwoLists(
    build_list([1, 2, 4]),
    build_list([1, 3, 4])
)
assert linked_list_to_list(head) == [1, 1, 2, 3, 4, 4]  # Standard merge case

# Example 2
head = solution.mergeTwoLists(
    build_list([]),
    build_list([])
)
assert linked_list_to_list(head) == []  # Both lists empty

# Example 3
head = solution.mergeTwoLists(
    build_list([]),
    build_list([0])
)
assert linked_list_to_list(head) == [0]  # One empty list

# Different lengths
head = solution.mergeTwoLists(
    build_list([1, 2]),
    build_list([3, 4, 5, 6])
)
assert linked_list_to_list(head) == [1, 2, 3, 4, 5, 6]  # Unequal sizes

# Duplicate values
head = solution.mergeTwoLists(
    build_list([1, 1, 1]),
    build_list([1, 1])
)
assert linked_list_to_list(head) == [1, 1, 1, 1, 1]  # Repeated values

# Negative numbers
head = solution.mergeTwoLists(
    build_list([-10, -3, 0]),
    build_list([-5, 2])
)
assert linked_list_to_list(head) == [-10, -5, -3, 0, 2]  # Negative values

# All elements from one list smaller
head = solution.mergeTwoLists(
    build_list([1, 2, 3]),
    build_list([10, 11, 12])
)
assert linked_list_to_list(head) == [1, 2, 3, 10, 11, 12]  # No interleaving

# Single element lists
head = solution.mergeTwoLists(
    build_list([5]),
    build_list([1])
)
assert linked_list_to_list(head) == [1, 5]  # Minimal non-empty lists
Test Why
[1,2,4] and [1,3,4] Standard interleaving merge
[] and [] Verifies handling of completely empty input
[] and [0] Verifies one empty list
Different length lists Ensures remaining nodes append correctly
Duplicate-heavy lists Confirms duplicates are preserved
Negative values Ensures ordering works with negatives
Non-overlapping ranges Tests direct append behavior
Single-element lists Minimal non-empty input

Edge Cases

One or both lists are empty

A common linked list bug happens when code assumes nodes always exist. If one list is None, dereferencing .val would crash.

This implementation handles the case naturally because the merge loop only runs while both lists are non-empty:

while list1 and list2:

If either list is empty initially, the algorithm skips directly to attaching the remaining list.

Duplicate values

The lists may contain repeated numbers such as:

[1,1,1]
[1,1]

A buggy implementation might accidentally skip duplicates or break ordering.

This solution explicitly allows equality:

if list1.val <= list2.val:

That guarantees duplicates are preserved correctly in the merged output.

One list finishes much earlier

Consider:

list1 = [1]
list2 = [2,3,4,5]

A common mistake is forgetting to append the remaining nodes after the main loop ends.

This implementation handles that with:

if list1:
    tail.next = list1
else:
    tail.next = list2

Since the remaining portion is already sorted, attaching it directly preserves correctness.