Merge Two Sorted Linked Lists

Table of Contents +

This one looks simple, but it trips up a lot of people in interviews. You have two lists that are already sorted. The interviewer wants to see if you can join them into one sorted list without making a mess of the pointers. So they are really testing how calm you stay when you have to move node links around by hand.

🔗 The Problem

You are given two linked lists. Both are already sorted in increasing order. You have to merge them into one single list that is also sorted. You should reuse the existing nodes, not copy values into a new array.

Here is what the input and output look like:

Input:
  List A: 1 -> 3 -> 5
  List B: 2 -> 4 -> 6

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

See, both lists are sorted on their own. The job is to walk through both at the same time and pick the smaller front node each time.

🐢 The Simple Idea First

One simple way is to dump all the values into an array. Then you sort the array. Then you build a fresh list from it.

It works, but it is not what they want. You are throwing away the fact that the lists are already sorted. Sorting again costs you extra time you did not need to spend. And building a brand new list wastes memory when the nodes are right there in front of you.

So in an interview this answer feels lazy. Let us do the smarter one.

⚡ The Better Approach: Walk Both Lists Together

The trick is to keep one pointer on the front of each list. Compare the two front nodes. The smaller one goes next in the answer. Then move that pointer forward by one. Repeat.

The tricky part is the very first node of the answer. You do not know yet whether it comes from list A or list B. To avoid writing special code just for that first node, we use a dummy node. A dummy node is a fake node we put at the start. We never use its value. We just attach real nodes after it. At the end, the real answer is whatever comes after the dummy.

We also keep a tail pointer. The tail always points to the last node we have attached so far. Each time we pick a node, we hang it off tail, then move tail to that new node.

Tip

The dummy node is the whole point of this problem. Without it you have to write an extra if just to set the head of the result. With it, every node is attached the same way. Mention this out loud in the interview. It shows you know the trick.

Steps to Merge

Make a dummy node. Set a tail pointer to dummy.
While both lists still have nodes, compare the two front nodes.
Attach the smaller node to tail.next, then move tail to that node.
Move forward the list pointer you just took the node from.
When one list runs out, attach the whole remaining list to tail.next.
Return dummy.next. That skips the fake node and gives the real head.

Here is the full code. It builds two sorted lists, merges them, and prints the result.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

# A single node of the linked list
class Node:
    def __init__(self, value):
        self.data = value
        self.next = None

# Merge two sorted lists into one sorted list
def merge_sorted(a, b):
    dummy = Node(0)   # fake node, value is never used
    tail = dummy      # tail tracks the last attached node

    while a is not None and b is not None:
        if a.data <= b.data:
            tail.next = a    # attach the smaller node
            a = a.next       # move that list forward
        else:
            tail.next = b
            b = b.next
        tail = tail.next     # move tail to the node we just added

    # One list is empty now; attach whatever is left
    tail.next = a if a is not None else b

    return dummy.next        # skip the fake node

def print_list(head):
    parts = []
    while head is not None:
        parts.append(str(head.data))
        head = head.next
    print(" -> ".join(parts))

# List A: 1 -> 3 -> 5
a = Node(1)
a.next = Node(3)
a.next.next = Node(5)

# List B: 2 -> 4 -> 6
b = Node(2)
b.next = Node(4)
b.next.next = Node(6)

merged = merge_sorted(a, b)
print_list(merged)

The output of the above code will be:

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

⏱️ Time and Space Complexity

Say list A has n nodes and list B has m nodes. Here is how the two approaches compare:

Approach	Time	Space
Copy to array, sort, rebuild	O((n + m) log(n + m))	O(n + m)
Dummy node + tail pointer	O(n + m)	O(1)

The dummy node way visits each node exactly once. So the time is just the total number of nodes. And it reuses the existing nodes, so the extra space is only the one dummy node, which is O(1).

Note

Notice we wrote a.data <= b.data, not a.data < b.data. Using <= keeps the order stable when two values are equal. It does not change correctness here, but stable behavior is a nice thing to mention.

🧩 Key Takeaways

✅ The lists are already sorted, so do not sort again. Just walk both fronts and pick the smaller one.
✅ A dummy node removes the special case for the first node. Every node gets attached the same way.
✅ The tail pointer always points to the last attached node, so you never lose your place.
✅ When one list runs out, attach the rest of the other list in one step. Do not loop through it.
✅ This runs in O(n + m) time and O(1) extra space because you reuse the nodes.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Reverse a Linked List
Merge Two Sorted Arrays

Previous Find the Middle of a Linked List Next Remove the Nth Node from the End

Share & Connect

Share on LinkedIn