Introduction

Merging two sorted linked lists is a classic pointer-manipulation problem. Because each input list is already sorted, the merge can be done in one linear pass by repeatedly choosing the smaller current node and attaching it to the output list.

The Core Idea

Suppose you have:

• list A: 1 -> 3 -> 5
• list B: 2 -> 4 -> 6

You do not need to resort all nodes. Instead, compare the current heads of the two lists:

• take 1, because it is smaller than 2
• then compare 3 and 2
• take 2
• continue until one list is exhausted

At the end, append the remaining nodes from the non-empty list.

This works because both inputs are already sorted.

Iterative Solution with a Dummy Node

The cleanest implementation uses a dummy head node so you do not need special-case logic for the first real element.

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6
7def merge_two_lists(list1, list2):
8    dummy = ListNode()
9    tail = dummy
10
11    while list1 and list2:
12        if list1.val <= list2.val:
13            tail.next = list1
14            list1 = list1.next
15        else:
16            tail.next = list2
17            list2 = list2.next
18
19        tail = tail.next
20
21    tail.next = list1 if list1 else list2
22    return dummy.next

This reuses the existing nodes instead of creating a whole new list.

Building a Small Test

1def build_list(values):
2    dummy = ListNode()
3    tail = dummy
4    for value in values:
5        tail.next = ListNode(value)
6        tail = tail.next
7    return dummy.next
8
9
10def print_list(node):
11    values = []
12    while node:
13        values.append(str(node.val))
14        node = node.next
15    print(" -> ".join(values))
16
17
18a = build_list([1, 3, 5])
19b = build_list([2, 4, 6])
20merged = merge_two_lists(a, b)
21print_list(merged)

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6

Recursive Version

There is also an elegant recursive solution:

1def merge_two_lists_recursive(list1, list2):
2    if not list1:
3        return list2
4    if not list2:
5        return list1
6
7    if list1.val <= list2.val:
8        list1.next = merge_two_lists_recursive(list1.next, list2)
9        return list1
10    else:
11        list2.next = merge_two_lists_recursive(list1, list2.next)
12        return list2

This is concise and expressive, but the iterative version is often preferred in production because it avoids recursion-depth concerns and makes control flow easier to trace.

Complexity

If the two lists have lengths m and n:

• time complexity is O(m + n)
• extra space is O(1) for the iterative version

Each node is visited exactly once, and no sorting pass is needed.

Why Linked Lists Make This Interesting

The same merge idea works for arrays, but linked lists emphasize pointer management. You are not writing into indexed positions. You are relinking next references carefully.

That makes this problem a useful test of:

• list traversal
• pointer updates
• edge-case handling

It also appears inside merge sort on linked lists, where merging is the efficient final step after splitting.

Common Pitfalls

The most common mistake is forgetting to advance the tail pointer after attaching a node. That can create cycles or overwrite links incorrectly.

Another error is forgetting to append the remainder after one list ends. The merge loop stops when either list becomes empty, but the other list may still contain valid sorted nodes.

People also sometimes create new nodes unnecessarily when the problem allows reusing the existing ones. Reusing nodes is simpler and more memory efficient.

Finally, be careful with empty-list inputs. If either list is None, the result should simply be the other list.

Summary

• Merge two sorted linked lists by repeatedly taking the smaller head node.
• A dummy head node makes the iterative solution cleaner.
• The iterative version runs in O(m + n) time with O(1) extra space.
• A recursive version is elegant, but iterative code is often safer in practice.
• Correct tail updates and final remainder attachment are the key implementation details.