Introduction

This interview problem tests whether you can manipulate pointers cleanly rather than whether you can allocate memory. Because you are not allowed to create new nodes, the solution must reuse the existing nodes and relink them in sorted order.

The core idea: walk both lists and relink nodes

Suppose both input lists are already sorted in ascending order. At any point, the correct next node in the merged list is simply the smaller head node of the two current lists.

That means the algorithm is:

1. choose the smaller head as the merged head
2. keep a tail pointer to the last node in the merged list
3. repeatedly attach the smaller current node from the two lists
4. when one list ends, attach the remainder of the other list

No new nodes are required. You are only changing next references.

Python implementation without creating nodes

Here is a complete runnable example:

1class Node:
2    def __init__(self, value, next=None):
3        self.value = value
4        self.next = next
5
6
7def merge_sorted_lists(a: Node | None, b: Node | None) -> Node | None:
8    if a is None:
9        return b
10    if b is None:
11        return a
12
13    if a.value <= b.value:
14        head = a
15        a = a.next
16    else:
17        head = b
18        b = b.next
19
20    tail = head
21
22    while a is not None and b is not None:
23        if a.value <= b.value:
24            tail.next = a
25            a = a.next
26        else:
27            tail.next = b
28            b = b.next
29        tail = tail.next
30
31    tail.next = a if a is not None else b
32    return head

This solution is in-place with respect to node allocation. The nodes from the original lists become the nodes of the merged list.

Why this is O(n + m) and O(1) extra space

Each node is visited once. If the first list has n nodes and the second has m, the total work is O(n + m).

The extra space is O(1) because:

• no new nodes are created
• only a few pointer variables are used

That is exactly why this is a classic interview question. It checks whether you can produce the optimal linked-list merge instead of defaulting to array-style rebuilding.

A recursive version also reuses nodes

You can solve the same problem recursively:

1def merge_sorted_lists_recursive(a: Node | None, b: Node | None) -> Node | None:
2    if a is None:
3        return b
4    if b is None:
5        return a
6
7    if a.value <= b.value:
8        a.next = merge_sorted_lists_recursive(a.next, b)
9        return a
10    else:
11        b.next = merge_sorted_lists_recursive(a, b.next)
12        return b

This also avoids creating new nodes, but it uses call stack space. In interviews, the iterative version is often preferred because it keeps auxiliary space at O(1).

Example walk-through

Take:

List A: 1 -> 4 -> 7
List B: 2 -> 3 -> 8

The merge goes like this:

• choose 1 as head
• compare 4 and 2, attach 2
• compare 4 and 3, attach 3
• compare 4 and 8, attach 4
• compare 7 and 8, attach 7
• attach the remaining 8

Result:

1 -> 2 -> 3 -> 4 -> 7 -> 8

The important detail is that these are the original nodes, only re-threaded in a new order.

Common Pitfalls

The biggest mistake is allocating a brand-new merged list, which violates the main constraint of the problem.

Another common issue is losing track of the next node before reassigning pointers. Pointer updates must happen in a safe order.

People also forget to handle empty input lists. Those base cases should be checked immediately.

Finally, once one list is exhausted, do not keep comparing against None. Just attach the remaining tail of the other list directly.

Summary

• The correct solution reuses existing nodes and only rewires next pointers.
• Use a head pointer and a tail pointer to build the merged list in order.
• The iterative solution runs in O(n + m) time and O(1) extra space.
• A recursive solution also works but uses stack space.
• Handle empty lists and the final remaining tail carefully to avoid pointer bugs.