Problem

You are given the heads of two sorted singly linked lists, list1 and list2.

Your task is to merge them into one sorted linked list and return the head of the merged list.

The merged list must reuse the existing nodes from list1 and list2.

Examples

Example 1

Input: list1 = [1,2,4], list2 = [1,3,5]
Output: [1,1,2,3,4,5]

Example 2

Input: list1 = [], list2 = [1,2]
Output: [1,2]

Example 3

Input: list1 = [], list2 = []
Output: []

Constraints

0 <= length of each list <= 100
-100 <= Node.val <= 100

Approach

Since both linked lists are already sorted, we can compare their current nodes and repeatedly add the smaller one to the merged list.

To simplify the construction of the result, we create a dummy node. The dummy node acts as a temporary starting point, so we do not need separate logic for assigning the head of the merged list.

We also use a pointer called node, which always points to the last node in the merged list.

While both lists contain nodes:

  1. Compare list1.val and list2.val.
  2. Attach the smaller node to node.next.
  3. Move forward in the list from which the node was selected.
  4. Move the node pointer forward.

When one list becomes empty, the other list may still contain nodes. Because the remaining nodes are already sorted, we can attach the entire remaining list directly.

Finally, we return dummy.next, which is the actual head of the merged linked list.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy = node = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                node.next = list1
                list1 = list1.next
            else:
                node.next = list2
                list2 = list2.next

            node = node.next

        node.next = list1 or list2

        return dummy.next

Step-by-Step Walkthrough

Consider the following input:

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

Initially, the merged list is empty.

First comparison

list1 node: 1
list2 node: 1

Since 1 < 1 is false, the node from list2 is selected.

Merged list: [1]
list1: [1,2,4]
list2: [3,5]

Second comparison

list1 node: 1
list2 node: 3

The node from list1 is smaller.

Merged list: [1,1]
list1: [2,4]
list2: [3,5]

Third comparison

list1 node: 2
list2 node: 3

The node from list1 is selected.

Merged list: [1,1,2]
list1: [4]
list2: [3,5]

Fourth comparison

list1 node: 4
list2 node: 3

The node from list2 is selected.

Merged list: [1,1,2,3]
list1: [4]
list2: [5]

Fifth comparison

list1 node: 4
list2 node: 5

The node from list1 is selected.

Merged list: [1,1,2,3,4]
list1: []
list2: [5]

At this point, list1 is empty. We attach the remaining part of list2 directly.

Final merged list: [1,1,2,3,4,5]

Why Use a Dummy Node?

Without a dummy node, we would need additional conditions to determine which node should become the head of the merged list.

The dummy node provides a fixed starting point:

dummy = node = ListNode()

Here, both dummy and node initially point to the same temporary node.

  • dummy remains at the beginning.
  • node moves forward as nodes are added.
  • dummy.next points to the real head of the completed list.

The dummy node itself is not included in the final result.

Attaching the Remaining Nodes

After the loop finishes, at least one of the lists is empty.

node.next = list1 or list2

In Python, the expression list1 or list2 returns whichever list is not None.

This is equivalent to writing:

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

Because the remaining list is already sorted, there is no need to process its nodes individually.

Complexity Analysis

Let:

  • n be the number of nodes in list1.
  • m be the number of nodes in list2.

Time Complexity

O(n + m)

Each node is visited at most once.

Space Complexity

O(1)

The solution only uses a few pointers and reuses the existing linked-list nodes. No additional linked list is created.

Key Takeaways

This problem demonstrates several important linked-list techniques:

  • Using a dummy node to simplify list construction.
  • Updating pointers without creating unnecessary nodes.
  • Taking advantage of the fact that both input lists are sorted.
  • Attaching the unprocessed remainder of a list in one operation.

The dummy-node pattern used here is especially useful in linked-list problems involving insertion, deletion, partitioning, or merging.