---
title: "Linked list merge & reorder"
url: https://algopath.pro/patterns/linked-list-merge
language: en
summary: "Build the answer on a dummy node and take from the front of each list. That dummy removes every empty-list special case."
updated: 2026-08-24
---

# Linked list merge & reorder

Build the answer on a dummy node and take from the front of each list. That dummy removes every empty-list special case.

## How does Linked list merge & reorder work?

Create a dummy node that leads nowhere yet. Its next will end up being the real head.

Keep a tail pointer starting at the dummy. Every node is appended there.

Compare the front node of each list. Append the smaller one and step that list forward.

Move the tail to the node just appended. Repeat until one of the lists runs out.

Append whatever remains of the other list. It is already sorted, so no comparison is needed.

Return dummy.next at the end. No node was copied, only re-linked.

- `dummy, a = 1, b = 2` Merging [1, 4] with [2, 3]. The dummy holds nothing.
- `tail = 1, a = 4, b = 2` 1 is smaller than 2, so it is appended first.
- `tail = 2, b = 3` Now 4 against 2. The 2 goes next.
- `tail = 3, b = null` 3 beats 4 as well. The second list is now empty.
- `1, 2, 3, 4` The rest of the first list is appended in one step.

## When should you use Linked list merge & reorder?

- merge two sorted linked lists
- merge k sorted lists
- reorder a list (interleave front and back halves)
- rearrange nodes without copying values into an array
- dummy head / sentinel node

## What is Linked list merge & reorder confused with?

- **Linked list reversal** - Reversal flips the links inside one list. Merging re-links nodes across two lists.
- **Binary heap / priority queue** - With k lists a heap picks the smallest front in log k. With two lists one comparison is enough.
- **Fast sort (merge / quick)** - The merge step of merge sort is this exact loop. Here the lists arrive already sorted.
- **Fast & slow pointers** - Reordering starts by finding the middle, which is that pattern. The weave afterwards is this one.

## What is the time and space complexity of Linked list merge & reorder?

n plus m nodes gives O(n + m) time and O(1) space. Merging k lists with a heap costs O(N log k).

## A worked example of Linked list merge & reorder

### Reorder a list from both ends

Reorder a list as first, last, second, second last, and onward.

The nodes have to be relinked. Copying the values into an array is not allowed.

Find the middle with a slow and a fast pointer, then cut the list there.

Reverse the back half. Weave the two halves together one node at a time.

```javascript
function reorderList(head) {
    if (!head || !head.next) return head;

    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let second = slow.next;
    slow.next = null; // cut the list in two, or the weave loops forever

    let prev = null;
    while (second) {
        const next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }

    let first = head;
    while (prev) {
        const a = first.next;
        const b = prev.next;
        first.next = prev;
        prev.next = a;
        first = a;
        prev = b;
    }

    return head;
}
```

## Common mistakes with Linked list merge & reorder

- **Working without a dummy node** The first append then needs a special case for the empty result. A dummy deletes that branch.
- **Dropping the leftover tail** When one list empties, the other still holds nodes. Link the whole rest in one step.
- **Building new nodes** These problems expect the original nodes relinked. Copying doubles the memory for nothing.
- **Leaving a cycle behind** Cutting a list means setting some next to null. Skipping that makes the list loop.

## Which interview problems use Linked list merge & reorder?

- **Merge two sorted lists** The plain form: a dummy and one comparison per node.
- **Merge k sorted lists** A heap holds the front node of every list.
- **Sort list** Split at the middle, sort both halves, then merge.
- **Reorder list** Split, reverse the back half, then weave the two.
- **Add two numbers** Walk both lists together and carry the overflow.
- **Partition list** Two dummies, one for small values and one for the rest.
- **Intersection of two linked lists** Two walkers that swap lists at the end.

## JavaScript

```javascript
function mergeTwoLists(a, b) {
    const dummy = { next: null };
    let tail = dummy;
    while (a && b) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a || b;
    return dummy.next;
}
```

## Python

```python
def merge_two_lists(a, b):
    dummy = Node(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next
```

## PHP

```php
function mergeTwoLists(?Node $a, ?Node $b): ?Node {
    $dummy = new Node(0);
    $tail = $dummy;
    while ($a !== null && $b !== null) {
        if ($a->val <= $b->val) { $tail->next = $a; $a = $a->next; }
        else { $tail->next = $b; $b = $b->next; }
        $tail = $tail->next;
    }
    $tail->next = $a ?? $b;
    return $dummy->next;
}
```