Merge & Sort

Merge Two Sorted Lists

Create a dummy head node. Compare the fronts of both lists, attach the smaller one to the result, and advance that list's pointer. Repeat until one list is exhausted, then attach the remainder.

O(n + m)

O(1)

How It Works

Merging two sorted lists exploits a key property of linked nodes: they can be relinked instead of copied. Create a dummy head and a tail pointer. While both lists are non-empty, compare their front nodes, attach the smaller to the tail, and advance both the tail and that list's pointer. When one list empties, attach the other's remainder in a single assignment — it is already sorted and linked.

The result is O(m + n) time and O(1) extra space, whereas merging arrays needs O(m + n) scratch space. This routine is the merge step of list merge sort and, applied pairwise or via a heap, the engine behind Merge k Sorted Lists.

Step-by-Step Visualization

Merge two sorted lists: [1,3,5] and [2,4,6]

Compare1 vs 2

1/4

Code

Java

static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  ListNode dummy = new ListNode(0);
  ListNode curr = dummy;

  while (l1 != null && l2 != null) {
    if (l1.val <= l2.val) {
      curr.next = l1;
      l1 = l1.next;
    } else {
      curr.next = l2;
      l2 = l2.next;
    }
    curr = curr.next;
  }

  curr.next = (l1 != null) ? l1 : l2;
  return dummy.next;
}

Tips & Gotchas

1Create a dummy head to simplify edge cases

2Compare fronts of both lists, attach the smaller one

3When one list is exhausted, attach the remainder of the other

Practice Problems

1Merge Two Sorted Lists
2Merge k Sorted Lists
3Sort List
4Merge Sorted Array

About the Merge & Sort Pattern

Combine sorted linked lists or sort an unsorted one. Unlike arrays, linked lists can be merged in O(1) extra space by re-pointing nodes.

Key insight

Most linked list problems are about pointer manipulation. Draw it out! Fast & slow pointers detect cycles and find midpoints. In-place reversal is the other core technique.

Common Linked List Interview Problems

Reverse Linked List
Merge Two Sorted Lists
Linked List Cycle
Remove Nth Node From End
LRU Cache
Reorder List

Frequently Asked Questions

What does the dummy head buy me?

Without it, the result's head must be chosen with a special comparison before the loop, and every attachment needs an is-this-the-first-node check. The dummy makes the loop body uniform from the first iteration, and the answer is simply dummy.next.

What is the best strategy for merging k lists?

Two good options: a min-heap over the k current front nodes gives O(N log k), or pairwise divide-and-conquer merging — merge lists in pairs, then merge the results — also O(N log k). Merging lists one after another into an accumulator degrades to O(Nk) and is the answer to avoid.

Which comparison keeps the merge stable?

Use <= when comparing the two fronts so that ties take from the first list. Stability rarely changes correctness for plain integers, but it matters when nodes carry payloads and is a detail interviewers notice.