How to Merge Linked Lists

What Does Merging Linked Lists Mean?

Merging linked lists means combining two linked lists into a single list while preserving a required ordering. A common data structures problem is to merge two sorted linked lists into one sorted linked list.

For example, suppose the first list contains:

1 → 4 → 7 → null

And the second list contains:

2 → 3 → 8 → null

The merged result should be:

1 → 2 → 3 → 4 → 7 → 8 → null

The important part is that we do not need to copy all values into an array and sort them. We can use the ordering that already exists in both lists.

The Two-Pointer Idea

Because both input lists are already sorted, compare their current nodes and select the smaller one. Then advance the pointer belonging to the selected node.

For:

List A: 1 → 4 → 7
List B: 2 → 3 → 8

The first comparison is between 1 and 2. Since 1 is smaller, it becomes the next node in the merged list. The pointer for List A then moves to 4.

Result: 1
A → 4 → 7
B → 2 → 3 → 8

Next, compare 4 and 2. The smaller value is 2, so it is attached to the result.

Result: 1 → 2
A → 4 → 7
B → 3 → 8

Continue this process until one list is exhausted.

Iterative Merge Using a Dummy Node

A dummy node is a convenient technique for building the merged list. It provides a stable starting point so that the code does not need separate logic for inserting the first node.

function mergeSortedLists(list1, list2) {
  const dummy = new Node(0);
  let current = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.data <= list2.data) {
      current.next = list1;
      list1 = list1.next;
    } else {
      current.next = list2;
      list2 = list2.next;
    }

    current = current.next;
  }

  current.next = list1 !== null ? list1 : list2;

  return dummy.next;
}

Notice that the function attaches the existing nodes directly. It does not create a new node for every value.

Why Use a Dummy Node?

Without a dummy node, the first selected node has to be handled separately because the merged list does not yet have a head.

A dummy node changes the process into a consistent operation:

dummy → selected node → selected node → selected node

Once merging is complete, dummy.next is the actual head of the merged list.

Handling the Remaining Nodes

The comparison loop stops when either list reaches null. At that point, all nodes from the other list can be attached directly because they are already sorted.

current.next = list1 !== null ? list1 : list2;

For example:

List A: 1 → 3 → null
List B: 2 → 4 → 5 → 6 → null

After comparisons:

Result: 1 → 2 → 3
List B: 4 → 5 → 6

Attach the remainder:

Result: 1 → 2 → 3 → 4 → 5 → 6

Complete JavaScript Example

The following example defines a node, creates two sorted lists, and merges them.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

function mergeSortedLists(list1, list2) {
  const dummy = new Node(0);
  let current = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.data <= list2.data) {
      current.next = list1;
      list1 = list1.next;
    } else {
      current.next = list2;
      list2 = list2.next;
    }

    current = current.next;
  }

  current.next = list1 !== null ? list1 : list2;

  return dummy.next;
}

function printList(head) {
  const values = [];
  let current = head;

  while (current !== null) {
    values.push(current.data);
    current = current.next;
  }

  console.log(values.join(' → '));
}

const list1 = new Node(1);
list1.next = new Node(4);
list1.next.next = new Node(7);

const list2 = new Node(2);
list2.next = new Node(3);
list2.next.next = new Node(8);

const merged = mergeSortedLists(list1, list2);

printList(merged);
// 1 → 2 → 3 → 4 → 7 → 8

Merging Empty Lists

A good implementation should handle empty input lists without requiring special code from the caller.

If both lists are empty:

list1 = null
list2 = null

result = null

If only the first list is empty:

list1 = null
list2 = 2 → 5 → 9

result = 2 → 5 → 9

The same applies when the second list is empty. The remaining list can simply be returned.

Handling Duplicate Values

Sorted lists can contain duplicate values. The merge algorithm handles them naturally. Using <= when comparing values means the node from the first list is selected when both values are equal.

List A: 1 → 3 → 5
List B: 1 → 3 → 6

Merged: 1 → 1 → 3 → 3 → 5 → 6

No duplicate values need to be removed unless the problem specifically requires unique values.

Recursive Approach

The same merge logic can be expressed recursively. Compare the heads of the two lists, keep the smaller node, and recursively merge the remainder.

function mergeSortedListsRecursive(list1, list2) {
  if (list1 === null) {
    return list2;
  }

  if (list2 === null) {
    return list1;
  }

  if (list1.data <= list2.data) {
    list1.next = mergeSortedListsRecursive(
      list1.next,
      list2
    );

    return list1;
  }

  list2.next = mergeSortedListsRecursive(
    list1,
    list2.next
  );

  return list2;
}

The recursive version is concise and closely matches the definition of the merge process, but it uses call-stack space for each recursive step.

Iterative vs Recursive Merge

Here, n and m represent the lengths of the two input lists. Every node needs to be considered at most once during the merge.

Does Merging Create New Nodes?

The iterative algorithm shown above does not create new nodes for the merged values. It reconnects the existing nodes by changing their next references.

Conceptually:

Before:

A: 1 → 4 → 7
B: 2 → 3 → 8

After:

1 → 2 → 3 → 4 → 7 → 8

The nodes themselves are reused. This is one reason linked lists can be convenient for pointer-based operations.

Merging Unsorted Linked Lists

The two-pointer merge technique depends on both input lists already being sorted. If the lists are unsorted, simply comparing the current nodes will not produce a sorted result.

For unsorted lists, one possible strategy is to combine their values and sort them, or sort each list first and then merge them. The appropriate approach depends on the requirements and available constraints.

Merge Operation and Linked List Structure

The key operation during merging is changing a node's next reference. Understanding this reference manipulation is important because the algorithm does not shift elements like an array would.

current.next = list1;

This statement attaches the selected node to the result. The pointer is then advanced:

current = current.next;

Keeping these pointer updates in the correct order prevents nodes from being skipped or disconnected.

Common Mistakes When Merging Linked Lists

• Assuming the input lists are sorted when the problem does not guarantee it.
• Forgetting to advance the pointer of the list whose node was selected.
• Forgetting to advance the result pointer after attaching a node.
• Not attaching the remaining nodes after one list becomes empty.
• Creating unnecessary copies of every node.
• Returning the dummy node instead of dummy.next.
• Breaking links by changing references in the wrong order.

Merge Two Lists Step by Step

Consider these lists:

A: 1 → 4 → 7
B: 2 → 3 → 8

Applications of Merging Linked Lists

Merging sorted linked lists is useful beyond a basic data structures exercise. It forms an important building block for algorithms that combine already sorted sequences.

• Merging sorted datasets.
• Combining ordered streams of records.
• Merge sort implementations for linked lists.
• Combining results from multiple sorted sources.
• Linked list interview and coding challenge problems.

Connection to Merge Sort

The merge operation is a fundamental part of merge sort. Merge sort divides a collection into smaller portions, sorts those portions, and then combines the sorted portions using a merge operation.

For linked lists, merging is especially useful because nodes can be connected directly without shifting elements as they would need to be in an array.

Interview Pattern to Remember

When you see a problem that asks you to combine two sorted linked lists, immediately look for the two-pointer pattern:

1. Create a dummy node.
2. Keep a current pointer.
3. Compare the two current nodes.
4. Attach the smaller node.
5. Advance the selected list.
6. Advance current.
7. Attach the remaining list.
8. Return dummy.next.

Key Takeaways

• Merging combines two linked lists into a single list.
• The standard two-pointer merge assumes both input lists are sorted.
• At each step, attach the smaller current node to the result.
• A dummy node simplifies handling the first node of the merged list.
• The iterative approach runs in O(n + m) time and O(1) extra space.
• The recursive approach also takes O(n + m) time but uses call-stack space.
• Remaining nodes can be attached directly after one list is exhausted.
• The same merge operation is an important component of merge sort.