Problem Statement

Given the heads of two sorted singly linked lists list1 and list2, return the head of a new sorted list that merges the nodes of list1 and list2. The new list should be made by splicing together the nodes of the first two lists. You may assume the input lists are sorted in non-decreasing order.

How the Algorithm Works

💡 One Sentence Rule (Key Insight)

Use two pointers to traverse both sorted lists simultaneously, always linking the smaller current node to the merged list.

This rule captures the ESSENCE of the algorithm. Every step we take follows from this rule.

Algorithm Overview

The merge operation exploits the fact that both input lists are already sorted. By maintaining pointers to the current position in each list, we can determine which node should come next in the merged result by simple comparison. A dummy node simplifies the construction by providing a fixed starting point.

Step-by-Step Process

At each iteration:

  1. Compare current nodes from both lists ← Choose the smaller value to maintain sorted order
  2. Link the smaller node to the merged list ← Build the result by connecting nodes
  3. Advance the pointer of the chosen list ← Move forward in the list we took from
  4. Advance the tail pointer ← Track the end of our merged list

After one list is exhausted:

  • Append remaining nodes from the non-empty list ← All remaining nodes are already sorted and greater than merged nodes

Input

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

Output

[1,1,2,3,4,4]

Solution

def merge_two_lists(list1, list2):
    dummy = ListNode()
    tail = dummy
    
    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
    
    if list1:
        tail.next = list1
    elif list2:
        tail.next = list2
    
    return dummy.next

Complexity Analysis

Time Complexity: O(n + m)

  • Each node from both lists is visited exactly once
  • Linear time proportional to total number of nodes

Space Complexity: O(1)

  • Only uses a few pointers (dummy, tail, list1, list2)
  • No additional data structures proportional to input size
  • Note: The merged list reuses existing nodes, not counted as auxiliary space

Applying the One Sentence Rule

The general linked list pattern:

Use linked list manipulation whenever you need to restructure connections between nodes by tracking and updating pointers.

For Merge Two Sorted Lists:

  • What are we restructuring? We're building a new linked list by connecting existing nodes from two sorted lists.
  • What pointers do we track? We track pointers to the current position in each input list (list1, list2) and the end of our merged list (tail).
  • How do we update? At each step, we compare the current nodes, link the smaller one to our merged list, and advance that list's pointer.

Example: Start with list1 = [1,2,4] and list2 = [1,3,4]. Both point to nodes with value 1. We choose list1's node first, link it to our merged list, and advance list1 to node 2. Now we compare 2 vs 1, choose list2's node 1, link it, and advance list2 to node 3. This continues until one list is empty, then we append the remainder.

The algorithm works because:

  1. Sorted property is preserved - Always choosing the smaller node maintains sorted order
  2. Single pass is sufficient - We never need to backtrack because both lists are pre-sorted
  3. Pointer manipulation is efficient - We reuse existing nodes instead of creating new ones