Merge Two Sorted Lists Explained for Beginners: The Zipper Move, Step by Step

I bombed a phone screen with JPMorgan, and the worst part was that I got the right answer.

Forty minutes, working code, correct output on every test case they threw at me. I took the two linked lists, walked them into a Python array, concatenated the arrays, called sorted(), and rebuilt a linked list out of the result. The interviewer said "okay, that works," typed something I couldn't see, and I never heard back. It took me two more months and a lot of angry evenings to understand what I'd done wrong.

So here's the claim I want to earn over the next thousand words, stated plainly up front: the fastest way to merge two sorted lists is to never sort anything. Not sort faster. Not sort smarter. Sort zero times. What follows is merge two sorted lists explained for beginners — the slow version, written for someone who has never seen a dummy node and goes blank when an interviewer says "two pointers."

This problem shows up at 26+ companies. Workday, ServiceNow, Twilio, JPMorgan. It's labeled Easy, which is its own kind of cruelty, because Easy means you're expected to produce it cleanly under a timer while someone watches your cursor.

What "merge" means when both inputs are sorted

A linked list is a chain. Each link is a node holding two things: a value, and a pointer to the next node. The last node points at nothing. You cannot jump to the middle — you can only start at the head and walk forward, one .next at a time.

You're handed two of these chains. Both are already sorted, smallest to largest. You have to return one chain containing every node from both, also sorted.

Here's the example I'm going to carry all the way through this piece:

list1:  1 -> 4 -> 7
list2:  2 -> 3 -> 9
answer: 1 -> 2 -> 3 -> 4 -> 7 -> 9

And here's the trap in the wording. The word "sorted" reads like a description of the input — background detail, scene-setting. It isn't. It's the entire hint, sitting in plain sight in the first sentence. Every problem in this family hides the answer in an adjective.

Why concatenate-then-sort throws away the gift

The obvious move is the one I made. Flatten both lists into a single array, sort the array, rebuild. Let me be fair to it: on the small inputs these problems usually ship with, that code passes. It returns the right answer. That's precisely why it's dangerous — the failure is invisible until someone asks you to explain your complexity out loud.

Walk the cost. Copying both lists into an array is O(n + m). Sorting that array is O((n + m) log(n + m)). Rebuilding is O(n + m). Total time: O((n + m) log(n + m)). Extra space: O(n + m), because you built a whole second copy of the data.

Put real numbers on it. Merge two lists of 500,000 nodes each. That's a million values. The log factor is about 20. So you're doing roughly twenty million units of comparison work — plus allocating a million-element array — to produce an answer that needs about one million comparison steps and no new array at all.

But the complexity is the shallow reason. Here's the deep one.

Sorting is a general-purpose tool. It's built for data that could be in any order at all, which is why it can't do better than log-linear on comparisons. Your data is not in any order. Your data arrived pre-ordered. Calling a general sort on pre-sorted input is paying full price for information you were handed for free.

And there's a proof sitting right there. Merge sort runs in O(n log n). It gets that by splitting the array log n times and merging at each level. If merging two sorted lists actually cost O(n log n), merge sort itself would cost O(n log² n), and it doesn't. The whole edifice depends on merge being linear. So a linear merge must exist. You're not being asked to invent it — you're being asked to notice that it has to be there.

The reframe: look at two heads, and only two heads

Here's the one insight. Read it twice.

The smallest value you haven't used yet is always sitting at the head of one of the two lists. Never in the middle. Never at the back. Both lists are sorted, so each list's smallest remaining value is its front node. The overall smallest remaining value is therefore whichever of those two fronts is smaller.

That means you never search. You compare two numbers, take the smaller one, and repeat. This is why people call it the zipper: two rows of teeth, one slider, alternating pulls.

Trace it by hand with my example. Keep a finger on each list.

Six steps. Six values. One comparison each. Nothing revisited.

Now the second piece, which is the part nobody explains. Building the answer means saying "attach this node to the end of what I've built." That works for every node except the first one, because the first node has nothing behind it to attach to. So you end up writing an if answer is empty branch inside your loop, and that branch is where off-by-one bugs live.

The fix is a dummy node, also called a sentinel: a fake node holding a garbage value that sits in front of the answer purely so that position one has a predecessor like every other position. It exists to delete a special case. At the end you return dummy.next and throw the fake away.

The solution, line by line

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

def mergeTwoLists(list1, list2):
    # The sentinel. Its value is never used. It exists so that
    # "attach the next node" is the same operation every time,
    # including the very first time.
    dummy = ListNode(-1)

    # tail always points at the last node of the answer so far.
    tail = dummy

    # Only run while BOTH lists still have a head to compare.
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1     # take the node from list1
            list1 = list1.next    # advance ONLY list1
        else:
            tail.next = list2     # take the node from list2
            list2 = list2.next    # advance ONLY list2
        tail = tail.next          # the answer grew by exactly one node

    # One list is now empty. Whatever remains in the other is
    # already sorted and already larger than everything placed,
    # so it attaches in a single move. No loop needed.
    tail.next = list1 if list1 else list2

    # dummy was never part of the answer.
    return dummy.next

In plain English: dummy is scaffolding. tail is your pen — it marks where the next node gets written. The loop compares exactly two numbers, relinks one node, and steps forward. When either list runs dry, the loop stops and the survivor's entire remainder gets hooked on in one assignment.

The <= rather than < matters more than it looks. On ties it takes from list1 first, which keeps equal elements in their original relative order — stability. Nobody will fail you for <, but being able to say why you chose <= is the difference between reciting and understanding.

Time: O(n + m). Every node is looked at once and never again. Space: O(1). You allocate one dummy node regardless of input size. You are relinking the nodes you were given, not copying them.

And if both lists come in empty, dummy.next is None, which is the correct answer. The sentinel handled the empty case without a single line of code written for it.

The specific ways people get this wrong

Skipping the dummy and special-casing the head. You write if result is None: result = node else: tail.next = node inside the loop, and now you're tracking two things that can drift apart. The sentinel exists to delete that branch. Use it.

Forgetting to attach the remainder. The loop exits the moment either list empties. If you stop there, every node still sitting in the other list vanishes from your answer. That single line after the loop is not cleanup — it's part of the algorithm.

Advancing both pointers after taking one node. This is the most common bug I see, and it silently drops half your data. You took a node from one list. Only that list moved. The other list's head is still unconsumed and still needs to be compared next round.

Returning dummy instead of dummy.next. Your answer comes back with a stray -1 glued to the front. Fast to spot, embarrassing to hit live.

Once this is in your hands, you own more than one problem. It's the merge step of merge sort. It's the core of merging K sorted lists. It's how external sorting handles files too big for memory. That's what "Easy" is actually labeling — not the difficulty, but the leverage.

So learn the zipper until your fingers know it before your brain does. And then sit with the question I still can't answer, the one nobody's shown me convincing data on: does producing this cleanly in twenty minutes, on a shared screen, with a stranger taking notes, measure your ability to build software — or does it mostly measure whether someone told you this would be on the exam?