Merge two lists and remove the nth node from the end

Why it matters

Merging two sorted lists is a building block. Merge sort on a linked list is built from it, and so are many systems that combine sorted streams of records. Removing the nth node from the end is the standard interview test of pointer gaps. Both problems look easy until the first node causes trouble. The head of a result is hard to choose, the removed node may be the first one, and an empty list has no head at all.

This lesson solves both problems with a tool you met in lesson 2: the dummy head node. A dummy is a placeholder node that sits in front of the real list. It gives every node, including the first one, a predecessor. Once every node has a predecessor, the same few lines work everywhere. You will also see the recursive merge, which is shorter but uses stack space, and the gap technique, which finds a node from the end without counting the list.

The problem of the first node

Suppose you want to build a new list out of two sorted lists. You must decide which node comes first. You must then decide the next node, the one after that, and so on. Each decision appends one node to the result. The trouble is the very first append. Before it, there is no result yet, so there is no tail to link to.

One way to handle this is a special case. Write one if to pick the head, then a loop to fill the rest. That works, but it doubles the code and gives two places for bugs. Another way is the dummy head. You create a node that is not part of the answer, and you append to its next. The dummy is never returned. At the end, you return dummy.next, which is the real head. The first append is now the same as every other append, because it links to a node that exists.

The dummy lives on the stack. You create it as a plain object, Node dummy(0);, and you never call delete on it. The nodes you link after it are on the heap, and they belong to the result. This is the only time in this module where a node on the stack is linked into a heap list, so keep the rule clear: the dummy is a handle, and the nodes after it are real nodes that must be freed later.

Merging two sorted lists, iteratively

Two lists are sorted when their values increase from head to tail. The merge combines them into one sorted list. The idea is simple: compare the two front nodes, take the smaller, and move on. Keep a tail pointer on the result so each taken node is appended in O(1) time.

Think of two stacks of exam papers, each sorted by student number, lying on a desk. You pick up the top paper of whichever stack is smaller, and put it on your pile. You repeat until one stack is empty. Then you put the rest of the other stack on top of your pile, because it is already sorted. Nothing needs to be compared at that point.

Node* mergeSorted(Node* a, Node* b) {
    Node dummy(0);
    Node* tail = &dummy;
    while (a != nullptr && b != nullptr) {
        if (a->data <= b->data) {
            tail->next = a;      // take the node from list a
            a = a->next;
        } else {
            tail->next = b;      // take the node from list b
            b = b->next;
        }
        tail = tail->next;       // the result's tail moves onto the taken node
    }
    tail->next = (a != nullptr) ? a : b;   // attach whatever is left, already sorted
    return dummy.next;
}

Two things deserve attention. First, the comparison uses <=, so when the values are equal the node from a goes first. That keeps the merge stable, which means equal items keep their original order. Stability matters when the list holds records with more fields than the sort key. Second, the function does not allocate any new nodes. It relinks the existing ones. That is why the extra space is O(1), and why the caller must not free the nodes of a and b separately after the merge. The nodes now belong to one list.

Trace the merge of a = 1, 4, 6 and b = 2, 3, 7. The table shows the state at the top of each loop round. The result grows at the tail.

After round 5, a is nullptr, so the loop stops. The line tail->next = (a != nullptr) ? a : b; attaches the remaining node 7. The result is 1, 2, 3, 4, 6, 7. The function returns dummy.next, which points at node 1.

The loop runs while both lists have nodes, so it takes at most n plus m rounds, where n and m are the lengths. The time is O(n + m). Each round moves one of the pointers forward, so no node is visited twice.

A merge that forgets the last attachment, traced

The most common merge bug is a missing last line. Imagine a version of mergeSorted that stops after its loop and forgets tail->next = (a != nullptr) ? a : b;. Trace it on a = 1 and b = 2, 3.

Start with the dummy as the tail. Compare 1 and 2: 1 is smaller, so the tail's next becomes node 1 and a becomes nullptr. The tail moves to node 1. The loop test sees that a is nullptr, so it stops. The function returns dummy.next, which is node 1, and the result is 1 with its next still nullptr. Nodes 2 and 3 are not in the result. They still exist, still point at each other, and nothing frees them, so this is also a leak.

The output is 1 where it should be 1 2 3. No crash, no warning. The bug is visible only if you print the result and compare it with the expected list. This is why the tests in the earlier programs check an unequal-length pair, such as {1, 4, 6} with {2, 3, 7} and {} with {5, 8}. A merge that works only for equal lengths is a bug that a small test will expose at once.

The fix is the line that attaches the leftover nodes. Because the leftover list is already sorted, one assignment is enough. The loop does the comparing, and the single assignment handles the tail.

Merging, recursively

The recursive version reads more like the definition. The merge of two lists is the smaller front node, followed by the merge of the rest. The base cases are the empty lists: if one list is empty, the answer is the other list.

Node* mergeRec(Node* a, Node* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->data <= b->data) {
        a->next = mergeRec(a->next, b);   // a's front stays first; merge the rest
        return a;
    }
    b->next = mergeRec(a, b->next);       // b's front stays first; merge the rest
    return b;
}

Trace it on a = 1, 4 and b = 2, 3. The call compares 1 and 2. Since 1 is smaller, it calls mergeRec(node4, node2) for the rest of the list, and sets node 1's next to the result. The inner call compares 4 and 2. Node 2 is smaller, so it calls mergeRec(node4, node3), and sets node 2's next to the result. The next call compares 4 and 3, takes node 3, and calls mergeRec(node4, nullptr). That call sees b is null and returns node 4. So node 3's next is node 4. Unwinding gives the chain 1, 2, 3, 4.

The recursive version has no dummy and no tail pointer, because each call returns the head of its merged part and the caller links to it. It is short and easy to check. Its cost is the stack. The merge goes as deep as the total length, so it uses O(n + m) stack space. For very long lists, the iterative merge is safer, and interviewers often ask for it when they ask about memory.

The next picture shows the calls on the stack as the merge works. The visualizer uses a simpler list, but the pattern is the same: each call waits for the result of the call below it.

A complete merge program

Here is a runnable program that merges two lists with both versions and prints the results. It also tests an empty list, because an empty input is the most common edge case for a merge.

1 2 3 4 6 7
1 2 3 4 6 7
5 8
5 8

The third line of output shows the empty first list. The merge loop does not run at all, and the tail is the dummy, so dummy.next is the second list. That is the dummy head doing its job: the empty case needs no code.

Merge sort on a list, traced

Merge sort is a sorting method that splits a list in half, sorts each half, and merges the two sorted halves. It suits linked lists well, because merging needs no random access and no extra array. Lesson 3 gave you the middle, and this lesson gave you the merge, so you already have both pieces.

Trace it on 4, 2, 3, 1. The first job is to split the list into two halves that each have their own end. The slow and fast pointers find the middle, and the list is cut just before the second half starts. The first half is 4, 2 and the second half is 3, 1. The cut is what makes each half a list that ends with nullptr.

The table shows the levels of the recursion, from the whole list down to single nodes, and then the merges coming back up.

At level 3, merging 4 and 2 gives 2, 4, because 2 is smaller. Merging 3 and 1 gives 1, 3. At level 4, the two sorted halves are 2, 4 and 1, 3. The merge takes 1 from the second list, then 2 from the first, then 3 from the second, then 4 from the first. The result is 1, 2, 3, 4.

Each level of merging touches every node once, so the merging work per level is O(n). There are about log2(n) levels, so the total time is O(n log n). The recursion needs O(log n) stack space, and the merges reuse the nodes, so no node is copied. This is one of the few sorts that is O(n log n) in the worst case and needs no extra array.

Counting the gap: why n plus 1 is right

The gap technique depends on one number being exact. Here is the argument, with a concrete list so you can check it. Let the list have L nodes, numbered 1 to L, and let the dummy be position 0.

The fast pointer starts at position 0 and moves n plus 1 steps, so it stops at position n plus 1. The slow pointer starts at position 0. Both pointers then move one step at a time, so the distance between them stays at n plus 1 for the whole walk.

The walk stops when fast reaches the position after the last node, which is position L plus 1. At that moment slow has moved L plus 1 minus n minus 1 steps, which is L minus n. So slow is on position L minus n.

The target is the nth node from the end, which is position L plus 1 minus n. That is exactly one position after slow. So slow is on the node just before the target, which is what the unlinking needs.

Check it with L equal to 5 and n equal to 2. Slow ends on position 5 minus 2, which is 3. The target is position 5 plus 1 minus 2, which is 4. The node at position 4 is the second from the end of 1, 2, 3, 4, 5, which is 4, as expected. If you used a gap of n instead of n plus 1, slow would end on position 4, which is the target itself, and the wrong node would be unlinked. That is why the exact gap matters.

Merging k lists with a heap

Merging two lists is a special case of merging many. With k sorted lists, a min-heap can hold the current front node of each list. Repeatedly remove the smallest node from the heap, link it onto the result, and push the next node from the same list. Every node passes through the heap once. Each heap operation costs O(log k), so the total is O(N log k), where N is the total number of nodes. The heap has its own module, so this is only the outline. The shape is the merge pattern from this lesson, with a heap choosing the next front node instead of one comparison.

A simpler method merges the lists in pairs, like a knockout tournament, and repeats until one list is left. Each round halves the number of lists, and each round costs O(N), so the total is also O(N log k). Merging one list after another, as practice exercise 2 shows, costs O(k N) and is slower when k is large. In an interview, state the heap version first, and mention the pairwise version as the simpler alternative.

Removing the nth node from the end

The task is to remove the node that is n places from the end. The node that is 1 from the end is the last node. The node that is 2 from the end is the one before the last. To remove it, you need the node just before it, because that node's next must change. The predecessor of the nth node from the end is the node that is n plus 1 from the end.

A simple solution counts the nodes first, then walks to the right spot. That takes two passes. The one-pass solution uses two pointers with a gap. The fast pointer moves n plus 1 steps ahead of the slow pointer. Then both move together until the fast pointer runs off the end. When fast is nullptr, slow is at the predecessor of the target, because the gap between them was n plus 1 the whole time.

Node* removeNthFromEnd(Node* head, int n) {
    Node dummy(0);
    dummy.next = head;
    Node* fast = &dummy;
    Node* slow = &dummy;
    for (int i = 0; i <= n; i++) {    // move fast n + 1 steps ahead
        fast = fast->next;
    }
    while (fast != nullptr) {          // move both until fast runs off the end
        fast = fast->next;
        slow = slow->next;
    }
    Node* target = slow->next;         // the node to remove
    slow->next = target->next;         // bypass it
    delete target;
    return dummy.next;
}

Why does the dummy matter here? The target may be the head. If n equals the length of the list, the node to remove is the first real node, and the predecessor of the head does not exist unless there is a dummy. With the dummy, the predecessor is the dummy itself. The final return dummy.next gives the correct new head in every case, including the case where the head was removed.

Trace it on 1, 2, 3, 4, 5 with n equal to 2. The target is node 4, the second node from the end. The table shows the two pointers.

With the loop stopped, slow is node 3, which is the predecessor of node 4. The code sets target to node 4 and then bypasses it. The list becomes 1, 2, 3, 5, which is correct because 4 was the second node from the end.

Now trace the edge case where n equals the length. The list is 1, 2, 3, 4, 5 and n is 5. The gap is 6 steps. Fast starts at the dummy and moves through nodes 1 to 5, then to nullptr, which is the sixth step. Slow never moves, so it stays on the dummy. The target is dummy.next, which is node 1. Bypassing it sets dummy.next to node 2, and the function returns node 2 as the new head. The list is 2, 3, 4, 5.

The gap technique uses O(n) time, because fast walks the list once, and O(1) extra space. It never counts the nodes, so it works without knowing the length.

The program that removes nodes

Here is the runnable program. It removes the second node from the end of a five node list, the fifth node from the end (the head), and then the only node of a one node list. The last case shows how the dummy keeps the code the same when the list becomes empty.

1 2 3 5
2 3 4 5
(empty)

Look at the last case. The one node list has the head as its only node. The gap is 2 steps, so fast runs off the end after the second step, and the walk loop does not run. The target is node 7, the predecessor is the dummy, and dummy.next becomes nullptr. The function returns nullptr, and print shows (empty). No special branch for the one-node list was needed.

Merge sort on a list, as a program

The next program puts the merge sort idea into code. The split function cuts the list in half using a slow and a fast pointer, and sortList sorts each half recursively before merging. The mergeSorted function is the one from this lesson.

1 2 3 4
5 6 7 8 9
1
(empty)

Trace split on 4, 2, 3, 1. The slow pointer starts on 4 and the fast pointer on 2. The loop runs once: slow moves to 2 and fast moves to 1. Then fast has no next, so the loop stops with slow on 2. The second half starts at 3, and the cut sets node 2's next to nullptr, which leaves 4, 2 and 3, 1 as two lists that each end properly. The recursion then sorts each pair and merges them, as the table earlier in this section showed.

Two more rewrites: duplicates and partition

Two smaller rewrites use the same pointer moves. The first removes repeated values from a sorted list. Because the list is sorted, equal values sit side by side, so you only compare each node with its next one. The head is never removed, so no dummy is needed.

Node* removeDuplicatesSorted(Node* head) {
    Node* cur = head;
    while (cur != nullptr && cur->next != nullptr) {
        if (cur->next->data == cur->data) {
            Node* dup = cur->next;   // save the duplicate
            cur->next = dup->next;   // skip it
            delete dup;              // free it
        } else {
            cur = cur->next;         // a new value: move on
        }
    }
    return head;
}

Trace 1, 1, 2, 3, 3. The cursor is on the first 1, and its next is also 1, so the second 1 is removed. The cursor is still on the first 1, and its next is now 2, so the cursor moves to 2. Then 2 is followed by 3, so the cursor moves to 3. The next node is also 3, so one 3 is removed. The cursor stays on 3, its next is nullptr, and the loop stops. The result is 1, 2, 3.

The second rewrite is partition. Given a value x, put every node below x first and every other node after them. Two dummy heads build two lists in order, and at the end they are joined. This is a good example of why dummies are useful: you need two possible first nodes, and neither has a predecessor until you add one.

Node* partitionList(Node* head, int x) {
    Node lowDummy(0), highDummy(0);
    Node* low = &lowDummy;
    Node* high = &highDummy;
    for (Node* cur = head; cur != nullptr; ) {
        Node* nxt = cur->next;   // save the rest of the old list
        cur->next = nullptr;     // detach cur from the old list
        if (cur->data < x) {
            low->next = cur;
            low = cur;
        } else {
            high->next = cur;
            high = cur;
        }
        cur = nxt;
    }
    low->next = highDummy.next;  // join the two groups
    return lowDummy.next;
}

The program below runs both rewrites. The first input has repeated values, and the second input has values on both sides of 4.

1 2 3
1 2 3 5 8 9
(empty)

In the partition, the nodes below 4 are 1, 2 and 3, and the others are 5, 8 and 9. Each group keeps its original order. The output is not fully sorted, because partition only splits the list around x.

Common mistakes and the messages you will see

The first merge mistake is to return the wrong head. A merge that starts with Node* head = a; and then decides which node to append loses the head when b is smaller. Use a dummy and return dummy.next.

The second merge mistake is to forget the last attachment. If the loop ends with a empty and b still holding nodes, the remaining nodes are not in the result. The list then prints too few values, with no error. The line tail->next = (a != nullptr) ? a : b; is what attaches them. Remove that line and test with lists of unequal length.

The third merge mistake is to allocate new nodes by copying, and then forget to free the originals. The one-pass merge reuses the nodes, so the original lists are gone. Freeing a or b after the merge deletes nodes that the result still uses. This shows as a use after free. The sanitizer reports heap-use-after-free on the line that reads the freed node, usually in the printing code, far from the merge. If a crash appears only after a merge, suspect that a list was freed too early.

The fourth merge mistake is to compare pointers instead of data. if (a <= b) compares addresses, which means nothing about the order of values. Compare the data fields.

The first removal mistake is an off-by-one in the gap. A gap of n, instead of n plus 1, leaves slow on the target itself, not on its predecessor. Then slow->next is the node after the target, and the wrong node is removed. Check the table above with n equal to 1, where the gap must be 2 steps.

The second removal mistake is to forget the dummy, so the head case is wrong. Without a dummy, removing the head needs a special branch, and it is easy to write the branch wrong. With the dummy, the code is correct in every case.

The third removal mistake is to return head instead of dummy.next. If the head was removed, the old head is freed, and returning it is a use after free. Always return dummy.next.

The fourth removal mistake is an n that is larger than the list. The fast pointer runs off the end during the gap loop and then reads nullptr->next. The sanitizer shows SEGV on unknown address with a small address. Assume n is valid, as the problem says, or check it while you build the gap.

A debugging walkthrough

Suppose a teammate changes the gap loop to for (int i = 0; i < n; i++). They call removeNthFromEnd on 1, 2, 3, 4, 5 with n equal to 2, and the output is 1 2 3 4. The second node from the end is 4, so the expected output is 1 2 3 5. The wrong node was removed. Here is how to find the cause.

First, write the expected result. Counting from the end, 5 is first and 4 is second, so the expected output is 1 2 3 5.

Second, trace the gap with the changed loop. Fast starts at the dummy. The loop now runs for i equal to 0 and 1, which is two steps. After step 1, fast is node 1. After step 2, fast is node 2. The gap is 2, but it should be n plus 1, which is 3.

Third, trace the walk with that gap. Fast is node 2 and not null, so both move. Fast goes to node 3 and slow goes to node 1. Fast goes to node 4 and slow to node 2. Fast goes to node 5 and slow to node 3. Fast goes to nullptr and slow to node 4, and the loop stops. Slow is on node 4, so target is node 5, which is the last node. The code removed 5 instead of 4.

Fourth, compare with the correct gap. With i <= n, fast takes three steps, so the walk ends with slow on node 3, the predecessor of node 4. The target is node 4, and the output is 1 2 3 5.

Fifth, the cause is the loop bound. A gap one short puts slow one node too far along, so it lands on the target's successor's predecessor, which is the target itself. Fix the bound to i <= n, write the two pointer positions on paper for n equal to 2, and rerun. The output becomes 1 2 3 5.

The lesson in the walkthrough is that the trace must match the code exactly. Writing out the loop bound makes the gap visible. Most bugs in pointer code are a single bound or a single comparison, so check those first.

Interview patterns for this lesson

Three patterns from this lesson come up again and again.

The first is the dummy head. Any problem where the head might change, or where the result's first node is chosen during the work, uses a dummy. Say it out loud: "I will use a dummy so the first node is not a special case." Interviewers mark that as a sign of a practised solution.

The second is the merge. Merging two sorted lists is a subroutine of merge sort on a list. Sorting a list of n nodes with merge sort takes O(n log n) time, because the list splits in half log n times and each level of merging costs O(n). A linked list suits merge sort well, because merging needs no random access and no extra array.

The third is the gap. Two pointers with a fixed distance find the node k places from the end in one pass. The same idea finds the middle in lesson 3, and the start of a cycle in a related method. When you see "from the end" in a list question, think of the gap.

Interviewers often follow up with "merge k sorted lists". The answer is a min-heap holding the front node of each list. Pop the smallest, append it, and push the next node from its list. Each of the N total nodes costs O(log k) heap work, so the total is O(N log k). The heap is covered in its own module, so for now, know the outline and the cost.

Another follow-up is "remove duplicates from a sorted list". Walk one pointer, and while the next node has the same value, skip it. The walk is O(n) and needs no dummy, because the head is never removed. Compare that with the unsorted version, which needs a set or a nested loop.

Practice

Try each exercise before opening its solution. For the merge exercises, draw both lists and move the pointers by hand.

1. Write Node* keepSingles(Node* head) for a sorted list. It removes every node whose value appears more than once, and keeps the values that appear exactly once. Example: 1, 1, 2, 3, 3, 3 becomes 2. Use a dummy head, because the first node can be removed.

Node* keepSingles(Node* head) {
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    Node* cur = head;
    while (cur != nullptr) {
        Node* last = cur;
        while (last->next != nullptr && last->next->data == cur->data) {
            last = last->next;          // last ends on the final node of this run
        }
        if (last == cur) {
            prev = cur;                 // a single value: keep it
        } else {
            Node* end = last->next;     // save the node after the run before freeing
            Node* p = cur;
            while (p != end) {
                Node* nxt = p->next;
                delete p;
                p = nxt;
            }
            prev->next = end;
        }
        cur = prev->next;
    }
    return dummy.next;
}

2. Write Node* mergeMany(vector<Node*> lists) that merges any number of sorted lists by repeatedly calling mergeSorted on pairs. Explain the cost if there are k lists of about n nodes each, when you merge them one after another.

Node* mergeMany(vector<Node*> lists) {
    if (lists.empty()) return nullptr;
    Node* result = lists[0];
    for (size_t i = 1; i < lists.size(); i++) {
        result = mergeSorted(result, lists[i]);
    }
    return result;
}

3. In partitionList, the line cur->next = nullptr; looks optional. Explain what would go wrong without it, using the list 5, 1 with x equal to 4.

4. Explain in two sentences why the merge uses <= and not < when comparing the two front nodes.

5. Find the bug in this merge: Node* bad(Node* a, Node* b) { Node* head = a->data <= b->data ? a : b; Node* tail = head; a = (head == a) ? a->next : a; ... }. Describe the failure, and give the fix idea in one sentence.

6. Write Node* removeNthFromStart(Node* head, int n) that removes the nth node counting from the head, where 1 is the first node. Use the dummy head, and return the new head.

Node* removeNthFromStart(Node* head, int n) {
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    for (int i = 1; i < n; i++) {
        prev = prev->next;
    }
    Node* target = prev->next;
    prev->next = target->next;
    delete target;
    return dummy.next;
}

7. In removeNthFromEnd, what is the value of slow when the walk loop stops for a list of length L and an n equal to L minus 1 (so the target is the second node from the head)? Give the answer in terms of L.

8. A friend says the gap technique needs to know the list length. Give a short argument that it does not.

9. Write bool isSortedAscending(Node* head) and explain why it is needed before calling mergeSorted.

bool isSortedAscending(Node* head) {
    for (Node* cur = head; cur != nullptr && cur->next != nullptr; cur = cur->next) {
        if (cur->data > cur->next->data) return false;
    }
    return true;
}

10. Describe, in plain steps, how merge sort on a linked list works, and state its time complexity.

What you now know

• A dummy head node gives every node a predecessor. Return dummy.next and the first-node case disappears.
• The iterative merge compares two front nodes, takes the smaller, and attaches whatever is left. It relinks nodes and uses O(1) extra space.
• The recursive merge is shorter and uses O(n) stack space. Use it when the code must be short and the lists are small.
• To remove the nth node from the end in one pass, move a fast pointer n plus 1 steps ahead of a slow pointer dummy, then walk both until fast is null. Slow stops on the predecessor.
• Return dummy.next, never the old head, because the old head may have been removed.
• Check the gap bound and the empty-list cases first when a pointer test fails.

The last lesson in the module covers doubly linked lists and circular lists, which add a second pointer to each node and close the chain into a loop.