16  Merge Two Sorted Linked Lists

Rank 14 · Pattern: two pointers plus sentinel node · Target: \(O(n+m)\) time, \(O(1)\) space

16.1 Problem definition

Given the heads of two sorted singly linked lists, merge all of their nodes into one sorted list and return its head.

16.2 Clarifying questions

1. In which direction are the input lists sorted?
2. Should the output reuse the existing nodes, and may their next references be changed?
3. Are duplicate values allowed?
4. Can either input list be empty?
5. Are the input lists acyclic and disjoint from one another?
6. Is any stability rule required when equal values occur in both lists?

16.3 Sample answers

1. Both lists are sorted in ascending order.
2. Yes. Reuse the data nodes and relink them; do not allocate a copied result.
3. Yes. Preserve every duplicate in the merged list.
4. Yes. If one list is empty, return the other; if both are empty, return null.
5. Yes. Each list ends at null, and they share no node objects.
6. No stability rule is required.

16.4 Special data structures: ListNode and sentinel

ListNode holds value and next. A sentinel (dummy) node is a temporary node placed before the output head. Java and Python relink object references; Rust moves existing Box<ListNode> values out of owned Option links. In all three versions, only the sentinel is newly allocated by the merge.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  S["sentinel: temporary node, not returned"]
  F["first real node"]
  M["zero or more middle nodes"]
  T["tail: final node in the merged prefix"]
  Z["null"]

  S --> F
  F --> M
  M --> T
  T --> Z

  classDef node fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  classDef reference fill:#ffffff,stroke:#555555,stroke-width:1.5px,stroke-dasharray:5 3,color:#222222;
  class F,M,T node;
  class S,Z reference;

It removes a special case for assigning the first result node. tail always means “the final node of the merged prefix.” The sentinel is not returned; sentinel.next is.

16.5 Approach and invariant

Compare the two current heads, append the smaller one to tail, advance that list, and advance tail. When one list ends, append the other list wholesale because it is already sorted.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  R["Two sorted input lists"]
  A1["a: node 1"]
  A3["a: node 3"]
  A7["a: node 7"]
  B2["b: node 2"]
  B4["b: node 4"]
  B6["b: node 6"]
  M["Relink the existing nodes in sorted order"]
  S["sentinel"]
  O1["node 1"]
  O2["node 2"]
  O3["node 3"]
  O4["node 4"]
  O6["node 6"]
  O7["tail: node 7"]
  Z["null"]

  R --> A1
  R --> B2
  A1 --> A3
  A3 --> A7
  B2 --> B4
  B4 --> B6
  A7 --> M
  B6 --> M
  M --> S
  S --> O1
  O1 --> O2
  O2 --> O3
  O3 --> O4
  O4 --> O6
  O6 --> O7
  O7 --> Z

  classDef node fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  classDef reference fill:#ffffff,stroke:#555555,stroke-width:1.5px,stroke-dasharray:5 3,color:#222222;
  class R,A1,A3,A7,B2,B4,B6,M,O1,O2,O3,O4,O6,O7 node;
  class S,Z reference;

The nodes below the sentinel are the same node objects that appeared in inputs a and b; they are drawn again only to show their final next ordering. The merge does not copy data nodes.

Invariant: the list after sentinel is a sorted merged prefix containing exactly the consumed nodes, tail is its last node, and a/b head the remaining sorted suffixes.

Choosing a on equality (<=) makes the merge stable with respect to the first list, though stability is usually not required.

16.6 Minimal solution

Java

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class MergeSortedListsSolution {
    static class ListNode {
        int value;
        ListNode next;
        ListNode(int value) { this.value = value; }
    }

    static ListNode merge(ListNode a, ListNode b) {
        ListNode sentinel = new ListNode(0);
        ListNode tail = sentinel;

        while (a != null && b != null) {
            if (a.value <= b.value) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }
        if (a != null) {
            tail.next = a;
        } else {
            tail.next = b;
        }
        return sentinel.next;
    }

    static ListNode list(int... values) {
        ListNode sentinel = new ListNode(0);
        ListNode tail = sentinel;
        for (int value : values) {
            tail.next = new ListNode(value);
            tail = tail.next;
        }
        return sentinel.next;
    }

    static List<Integer> values(ListNode head) {
        List<Integer> result = new ArrayList<>();
        for (; head != null; head = head.next) {
            result.add(head.value);
        }
        return result;
    }

    @Test public void twoEmptyListsProduceEmptyList() {
        assertNull(merge(null, null));
    }

    @Test public void emptyFirstListReturnsSecondByIdentity() {
        ListNode second = list(3, 4);
        assertSame(second, merge(null, second));
    }

    @Test public void emptySecondListReturnsFirstByIdentity() {
        ListNode first = list(1, 2);
        assertSame(first, merge(first, null));
    }

    @Test public void selectsSmallerHeadFromEitherList() {
        assertEquals(List.of(1, 2), values(merge(list(1), list(2))));
        assertEquals(List.of(1, 2), values(merge(list(2), list(1))));
    }

    @Test public void mergesAlternatingLists() {
        assertEquals(List.of(1, 2, 3, 4, 6, 7),
                     values(merge(list(1, 3, 7), list(2, 4, 6))));
    }

    @Test public void preservesDuplicateValues() {
        assertEquals(List.of(1, 1, 2), values(merge(list(1), list(1, 2))));
    }

    @Test public void reusesNodesAndAppendsTheRemainingSuffix() {
        ListNode first = list(1, 2);
        ListNode second = list(8, 9);
        ListNode merged = merge(first, second);

        assertSame(first, merged);
        assertSame(second, merged.next.next);
        assertEquals(List.of(1, 2, 8, 9), values(merged));
    }

    public static void main(String[] args) {
        JUnitCore.main("MergeSortedListsSolution");
    }
}

Python

import unittest


class ListNode:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def merge(first, second):
    sentinel = ListNode(0)
    tail = sentinel

    while first is not None and second is not None:
        if first.value <= second.value:
            tail.next = first
            first = first.next
        else:
            tail.next = second
            second = second.next
        tail = tail.next

    tail.next = first if first is not None else second
    return sentinel.next


def linked_list(*values):
    sentinel = ListNode(0)
    tail = sentinel
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return sentinel.next


def list_values(head):
    values = []
    while head is not None:
        values.append(head.value)
        head = head.next
    return values


class MergeSortedListsTests(unittest.TestCase):
    def test_two_empty_lists(self):
        self.assertIsNone(merge(None, None))

    def test_empty_first_list_returns_second_by_identity(self):
        second = linked_list(3, 4)
        self.assertIs(second, merge(None, second))

    def test_empty_second_list_returns_first_by_identity(self):
        first = linked_list(1, 2)
        self.assertIs(first, merge(first, None))

    def test_selects_smaller_head_from_either_list(self):
        self.assertEqual([1, 2], list_values(merge(linked_list(1), linked_list(2))))
        self.assertEqual([1, 2], list_values(merge(linked_list(2), linked_list(1))))

    def test_merges_alternating_lists(self):
        result = merge(linked_list(1, 3, 7), linked_list(2, 4, 6))
        self.assertEqual([1, 2, 3, 4, 6, 7], list_values(result))

    def test_preserves_duplicates(self):
        result = merge(linked_list(1), linked_list(1, 2))
        self.assertEqual([1, 1, 2], list_values(result))

    def test_reuses_nodes_and_appends_suffix(self):
        first = linked_list(1, 2)
        second = linked_list(8, 9)
        result = merge(first, second)
        self.assertIs(first, result)
        self.assertIs(second, result.next.next)


if __name__ == "__main__":
    unittest.main()

Rust

#[derive(Debug)]
pub struct ListNode {
    pub value: i32,
    pub next: Link,
}

pub type Link = Option<Box<ListNode>>;

impl ListNode {
    pub fn new(value: i32) -> Self {
        Self { value, next: None }
    }
}

pub fn merge(mut first: Link, mut second: Link) -> Link {
    let mut sentinel = Box::new(ListNode::new(0));
    let mut tail = &mut sentinel;

    while first.is_some() && second.is_some() {
        let take_first = first.as_ref().unwrap().value <= second.as_ref().unwrap().value;

        let mut node = if take_first {
            let mut node = first.take().unwrap();
            first = node.next.take();
            node
        } else {
            let mut node = second.take().unwrap();
            second = node.next.take();
            node
        };

        node.next = None;
        tail.next = Some(node);
        tail = tail.next.as_mut().unwrap();
    }

    tail.next = if first.is_some() { first } else { second };
    sentinel.next
}

#[cfg(test)]
mod tests {
    use super::*;

    fn list(values: &[i32]) -> Link {
        let mut head = None;
        for &value in values.iter().rev() {
            let mut node = Box::new(ListNode::new(value));
            node.next = head;
            head = Some(node);
        }
        head
    }

    fn values(mut head: &Link) -> Vec<i32> {
        let mut result = Vec::new();
        while let Some(node) = head {
            result.push(node.value);
            head = &node.next;
        }
        result
    }

    #[test]
    fn two_empty_lists() {
        assert!(merge(None, None).is_none());
    }

    #[test]
    fn empty_first_list_returns_second() {
        assert_eq!(vec![3, 4], values(&merge(None, list(&[3, 4]))));
    }

    #[test]
    fn selects_smaller_head_from_either_list() {
        assert_eq!(vec![1, 2], values(&merge(list(&[1]), list(&[2]))));
        assert_eq!(vec![1, 2], values(&merge(list(&[2]), list(&[1]))));
    }

    #[test]
    fn merges_alternating_lists() {
        let result = merge(list(&[1, 3, 7]), list(&[2, 4, 6]));
        assert_eq!(vec![1, 2, 3, 4, 6, 7], values(&result));
    }

    #[test]
    fn preserves_duplicates() {
        let result = merge(list(&[1]), list(&[1, 2]));
        assert_eq!(vec![1, 1, 2], values(&result));
    }
}

The list-building and value-collection helpers are test fixtures. In an interview prompt that supplies its own node type, type only the node-merging function.

16.7 High-value tests

A	B	Expected
empty	empty	empty
empty	3	3
1,3,7	2,4,6	1,2,3,4,6,7
1	1,2	1,1,2
1,2	8,9	1,2,8,9

16.8 Complexity and correctness

Each comparison consumes one node, and the remainder is linked once. Time is \(O(n+m)\). Only sentinel and pointer references are new algorithmic storage, so auxiliary space is \(O(1)\); existing nodes are reused.

The smaller current head is no greater than any unconsumed node in either sorted list, so appending it preserves sorted order and cannot skip a smaller value. When a list empties, every remaining node in the other list is at least the last appended value.

16.9 If the interviewer pushes

• A recursive solution is shorter but uses \(O(n+m)\) stack space.
• Merging \(k\) lists with a heap costs \(O(N\log k)\) for \(N\) total nodes; pairwise divide-and-conquer gives the same asymptotic bound.
• If mutation is forbidden, allocate new nodes, increasing space to \(O(n+m)\).

16.10 TDD interview script

Confirm ascending, acyclic, disjoint input lists; existing nodes must be relinked; duplicates are preserved; either input may be empty; and no equal-value stability rule is required. Then write this test list:

1. Both lists empty
2. First list empty
3. Second list empty
4. Either list owning the smaller head
5. Alternating values
6. Duplicate values
7. Remaining suffix reused by identity

Use one focused red–green–refactor cycle at a time. Linked-list value assertions establish ordering, while identity checks establish the no-copy contract in reference-based versions; Rust’s consuming ownership API makes node reuse explicit. Rerun the complete example after each change and do not assert a stability rule the contract does not require.

From book/src, run:

Java

./java/run.sh MergeSortedListsSolution

Python

./python/run.sh merge_sorted_lists_solution

Rust

./rust/run.sh merge_sorted_lists_solution

Introduce the sentinel as a simplification, not as an output node: it gives every appended node a predecessor, and the method returns sentinel.next. State that the remaining suffix can be attached wholesale once either input is exhausted.

16.10.1 Pseudocode

sentinel = temporary node
tail = sentinel

while a and b are both non-null:
    if a.value <= b.value:
        tail.next = a
        a = a.next
    else:
        tail.next = b
        b = b.next
    tail = tail.next

tail.next = whichever of a or b remains
return sentinel.next

The invariant is: the chain after the sentinel is a sorted merged prefix containing exactly the consumed nodes, tail is its last node, and a and b head the remaining sorted suffixes.

16.10.2 TDD sequence

Step	Test code added	Production code added or changed
1. No nodes	twoEmptyListsProduceEmptyList	Create a sentinel and return sentinel.next, initially null.
2. Only the second list	emptyFirstListReturnsSecondByIdentity	Attach the non-null remainder to tail; return the original second head.
3. Only the first list	emptySecondListReturnsFirstByIdentity	Generalize remainder selection to whichever input is non-null.
4. Either smaller head	selectsSmallerHeadFromEitherList	Compare current values, link the smaller node, advance its input pointer, and advance tail.
5. Repeated selection	mergesAlternatingLists	Loop while both lists remain, preserving sorted order across repeated branch changes.
6. Equal values	preservesDuplicateValues	Consume one equal-valued node at a time and retain every node; <= is a simple valid tie choice.
7. Whole suffix	reusesNodesAndAppendsTheRemainingSuffix	Link the already-sorted remainder once rather than copying or traversing it; identity assertions verify reuse.

This progression separates empty-list plumbing from the two-pointer comparison. Identity checks ensure that an apparently correct value sequence cannot conceal a copied implementation.