Skip to content

Volume ITechnology

4.9.2 — Merge Two Sorted Lists ​

LeetCode 21 · Easy · ★ Blind 75

The problem ​

You are given the heads of two linked lists, list1 and list2. Each list is already sorted from smallest to largest. Join them into one sorted list by re-linking the existing nodes, not by making new ones. Return the head of the joined list.

list1 = 1 → 2 → 4
list2 = 1 → 3 → 4
result: 1 → 1 → 2 → 3 → 4 → 4

list1 = (empty), list2 = (empty)   →  (empty)
list1 = (empty), list2 = 0         →  0

Each list has between 0 and 50 nodes.

What the problem is really asking ​

Think of two queues of people, each already lined up by height. You want one combined queue, also lined up by height. You look at the person at the front of each queue, send the shorter one to the combined queue, and repeat.

The smallest node overall must be the front of one of the two lists, because each list is sorted. So the real question is: at each step, which of the two front nodes is smaller?

The brute force, and where it wastes work ​

Copy every value into one array, sort it, and build a new list.

python
def mergeTwoLists(list1, list2):
    values = []
    for node in (list1, list2):
        while node:
            values.append(node.val)
            node = node.next
    values.sort()
    dummy = tail = ListNode()
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

This takes O((n + m) \log(n + m)) time for the sort and O(n + m) extra memory. It also makes new nodes, which the problem asked us not to do.

The waste in one sentence: it throws away the fact that both lists are already sorted, and sorts everything again from scratch.

The idea ​

Walk both lists at once. Compare the two front nodes, attach the smaller one to the result, and move that list forward by one. When one list runs out, attach whatever is left of the other one in a single step.

The dummy head ​

The first node is awkward. Every later node is attached with tail.next = node. But at the start there is no tail to attach to yet, so the first node would need its own special if.

The fix is a fake node placed in front of the result. It is called a dummy head. We attach everything to it, including the first real node, and at the end we return dummy.next, skipping the fake one.

dummy → 1 → 1 → 2 → 3 → 4 → 4
  ↑
  never part of the answer, just something to attach to

The dummy head removes the special case for the head from every linked-list problem where nodes are added or removed. It is the most useful habit in this chapter. You will see it again in 4.9.4, 4.9.6 and 4.9.11.

The solution ​

python
class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode()                     # (1)
        tail = dummy                           # (2)

        while list1 and list2:                 # (3)
            if list1.val <= list2.val:         # (4)
                tail.next = list1
                list1 = list1.next
            else:                              # (5)
                tail.next = list2
                list2 = list2.next
            tail = tail.next                   # (6)

        tail.next = list1 or list2             # (7)

        return dummy.next                      # (8)
ts
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode();                // (1)
  let tail = dummy;                            // (2)

  while (list1 && list2) {                     // (3)
    if (list1.val <= list2.val) {              // (4)
      tail.next = list1;
      list1 = list1.next;
    } else {                                   // (5)
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;                          // (6)
  }

  tail.next = list1 ?? list2;                  // (7)

  return dummy.next;                           // (8)
}

Line by line ​

(1) The dummy head. A fake node with no meaningful value. It is the one new node we create.

(2) tail points at the last node of the result so far. At the start, that is the dummy.

(3) Loop while both lists still have nodes. Once either one is empty, there is nothing left to compare.

(4) The front of list1 is smaller or equal. Attach it to the result, and move list1 forward to its next node.

We use <= rather than <. When the two values are equal, the node from list1 goes first. Either choice gives a correct answer here. But keeping equal items in their original order has a name, being stable, and it is what makes merge sort useful when sorting records by one field. So write it on purpose.

(5) Otherwise, the front of list2 is smaller. Attach it and move list2 forward.

(6) Move tail onto the node we just attached, so the next node goes after it.

(7) Attach the leftovers in one step. When the loop ends, at least one list is empty. The other one, if it has nodes left, is already sorted, and every node in it is at least as big as everything placed so far. So we can attach the whole remaining chain at once. No loop is needed.

In Python, list1 or list2 gives the first one that is not None. If both are None, it gives None, which is also fine. In TypeScript, ?? gives the left side unless it is null or undefined, and the right side otherwise.

(8) Skip the dummy. The real result starts at dummy.next.

Trace ​

Take list1 = 1 → 2 → 4 and list2 = 1 → 3 → 4.

StepFront of list1Front of list2AttachResult so far
111list1's 1 (equal, so list1 first)1
221list2's 11 → 1
32321 → 1 → 2
44331 → 1 → 2 → 3
544list1's 41 → 1 → 2 → 3 → 4
endempty4line (7) attaches list2's 41 → 1 → 2 → 3 → 4 → 4

Complexity, derived ​

Time. Each turn of the loop attaches exactly one node and moves past it, so the loop runs at most n + m times. Line (7) is a single assignment. So the time is O(n + m).

Space. The only new node is the dummy, plus two pointer variables. Every other node is re-linked, not copied. So the extra memory is O(1).

Edge cases ​

  • Both lists empty. The loop never runs. Line (7) attaches None. The answer is dummy.next, which is None.
  • One list empty. The loop never runs. Line (7) attaches the other list whole.
  • One list much longer. The loop stops when the short one runs out, and line (7) attaches the long tail in one step.
  • Equal values across the lists. Handled by <=.

The recursive version ​

python
def mergeTwoLists(self, l1, l2):
    if not l1: return l2                          # nothing left in l1
    if not l2: return l1                          # nothing left in l2
    if l1.val <= l2.val:
        l1.next = self.mergeTwoLists(l1.next, l2) # l1 goes first; merge the rest after it
        return l1
    l2.next = self.mergeTwoLists(l1, l2.next)
    return l2

It is shorter, and the two base cases handle the leftovers automatically. But each call waits on the call stack, so it uses O(n + m) memory and can crash on very long lists. This is the same trade-off as in 4.9.1.

Variations you will meet ​

  • Merge k Sorted Lists. Merge many lists at once. Either pair them up and merge the pairs again and again, or keep a heap of the k front nodes. See 4.9.10.
  • Sort List. Sort a linked list using merge sort. Split it in half with slow and fast pointers, sort each half, and use this page's code to merge them.
  • Merge Sorted Array. The array version. Fill the answer from the back, so you never overwrite a value you have not read yet.

The general lesson: when you build or edit a linked list, put a dummy node in front, so the first real node needs no special case.

What the interviewer will push on ​

"Why the dummy node?" So the first node needs no special case. This generalises to every linked-list problem that adds or removes nodes.

"What if one list is much longer?" The loop stops when the shorter one ends, and the rest is attached in one step, at no extra cost.

"Can you do it in O(1) extra memory?" The loop version already does. The recursive version does not.

"Why <=?" It keeps equal values in their original order, which is the stable property merge sort relies on.

One thing to volunteer: point out that this is the merge step of merge sort, and that linked lists are the one place where merge sort needs no extra memory at all. See 4.10.

Next: 4.9.3 Reorder List. Three different linked-list techniques, used one after another in a single problem.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet