How do you solve Merge Two Sorted Lists?

Initialize a dummy node to act as the start of the merged list and a tail pointer to track the last node in the merged list. While both lists have nodes, compare their current values, link the smaller node to tail.next, and advance the corresponding pointer and tail. After the loop, link the remaining nodes from the non-empty list to tail.next. Return dummy.next as the head of the merged list.

Merge Two Sorted Lists

Q: What is the time complexity of Merge Two Sorted Lists?

O(n + m). Each node from both lists is visited exactly once and linked into the merged list, resulting in linear time proportional to the total number of nodes.

Q: What pattern does Merge Two Sorted Lists use?

The Pattern: Linked List (Two-Pointer Merge) The Heuristic: When merging two sorted linked lists, use two pointers to traverse both lists simultaneously, always linking the smaller current node to the merged list and advancing that pointer, which guarantees a single linear pass with O(1) auxiliary space.

Easy In-place Reversal of a Linked List

Problem

Given the heads of two sorted singly linked lists list1 and list2, merge the two lists into one sorted list and return the head of the merged list.

The number of nodes in both lists is in the range [0, 50]
−100 ≤ Node.val ≤ 100
Both list1 and list2 are sorted in non-decreasing order

Example

Input: list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

The algorithm starts with two pointers at the heads of list1 and list2. It compares the current nodes: both have value 1. It chooses the node from list1 first, linking it to the merged list. Then it advances list1's pointer. Next, it compares 2 (list1) and 1 (list2), chooses 1 from list2, and advances list2. This process continues, always linking the smaller current node to the merged list and advancing that pointer. When one list is exhausted, the remaining nodes of the other list are appended directly. The final merged list is sorted and contains all nodes from both lists.

Approach

Straightforward Solution

A naive approach might create a new list and copy values from both lists, but this wastes space and time. Another naive approach is to concatenate and then sort, which is inefficient (O(n log n)).

Core Observation

Merging two sorted lists is fundamentally about repeatedly choosing the smaller current node from either list and linking it to the merged list, preserving sorted order.

Path to Optimal

The key insight is to use two pointers to traverse both lists simultaneously, always linking the smaller node to the merged list and advancing that pointer. This approach exploits the sorted property to merge in a single pass with O(n) time and O(1) auxiliary space.

Optimal Approach

Preview

Initialize a dummy node to act as the start of the merged list and a tail pointer to track the last node in the merged list. While both lists have nodes, compare their current values, link the smaller node to tail…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + m)

Each node from both lists is visited exactly once and linked into the merged list, resulting in linear time proportional to the total number of nodes.

Space

O(1)

The algorithm uses only a few pointers and does not allocate new nodes or data structures proportional to input size, achieving constant auxiliary space.

Pattern Spotlight

Linked List (Two-Pointer Merge)

When merging two sorted linked lists, use two pointers to traverse both lists simultaneously, always linking the smaller current node to the merged list and advancing that pointer, which guarantees a single linear pass with O(1) auxiliary space.

Solution

Python

1class Solution:
  def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
      dummy = ListNode()
      tail = dummy
5
      while list1 and list2:
          if list1.val < list2.val:
              tail.next = list1
              list1 = list1.next
          else:
              tail.next = list2
              list2 = list2.next
          tail = tail.next
14
      if list1:
          tail.next = list1
      elif list2:
          tail.next = list2
      
      return dummy.next

Step-by-Step Solution

Initialize Dummy Node and Tail Pointer to Build Merged List

3dummy = ListNode()
4tail = dummy

Objective

To create a starting point for the merged list and maintain a pointer to its last node for efficient appending.

Key Insight

Using a dummy node simplifies edge cases by providing a fixed starting node, avoiding special handling for the head of the merged list. The tail pointer always points to the last node in the merged list, enabling O(1) appends as nodes are linked.

Interview Quick-Check

Core Logic

The dummy node acts as a sentinel to simplify list construction, and the tail pointer tracks the end of the merged list for efficient linking.

Common Pitfalls & Bugs

Forgetting to initialize the tail pointer to the dummy node can cause incorrect linking or loss of the merged list head.

Iteratively Compare Nodes and Link the Smaller to the Merged List

To traverse both lists simultaneously, always appending the smaller current node to the merged list and advancing pointers accordingly.

Append Remaining Nodes from Non-Exhausted List to Complete Merge

To link any leftover nodes from either list after the other is fully traversed, completing the merged list.

Return the Head of the Merged List Skipping Dummy Node

To return the merged list starting from the first real node, excluding the dummy node.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 8 Critical

tail.next = list1

Link the smaller node (from list1) to the merged list.

Linking the smaller node preserves the sorted order and builds the merged list incrementally.

Line 11 Critical

tail.next = list2

Link the smaller node (from list2) to the merged list.

Linking the smaller node from list2 maintains the sorted order and continues building the merged list.

Line 13 Critical

tail = tail.next

Advance the tail pointer to the newly linked node.

Moving the tail pointer keeps it at the end of the merged list, enabling O(1) appends in subsequent iterations.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why is it safe to link the remaining nodes of one list directly after the other list is exhausted?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Merge Two Sorted Lists from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Merge Two Sorted Lists drill

or drill a free problem

1	`class Solution:`
2	`def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:`
3	`dummy = ListNode()`
4	`tail = dummy`
5
6	`while list1 and list2:`
7	`if list1.val < list2.val:`
8	`tail.next = list1`
9	`list1 = list1.next`
10	`else:`
11	`tail.next = list2`
12	`list2 = list2.next`
13	`tail = tail.next`
14
15	`if list1:`
16	`tail.next = list1`
17	`elif list2:`
18	`tail.next = list2`
19
20	`return dummy.next`