cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 41 of 218
Ideas this builds on
Linked lists41 / 218

Merge two sorted linked lists

Picture

For 1→4 and 2→3, every later node is at least its list’s front. Compare 1 and 2.

Predict

Must we allocate new nodes to merge?

Walk through the small example

No. The minimum remaining node must be one of two current fronts.

Mental model and complete Python solution

Each chain offers its smallest remaining value at the front. The smaller front is globally safe; attach it and repeat the same question.

What the function promises: Return a nondecreasing chain reusing nodes. Inputs are disjoint, acyclic, and sorted.

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

def build(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head

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

def merge_lists(left, right):
    dummy = tail = Node(None)
    while left is not None and right is not None:
        if left.value <= right.value:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left if left is not None else right
    return dummy.next

assert to_list(merge_lists(build([1,4]), build([2,3]))) == [1,2,3,4]

Work and storage: O(n+m) time and O(1) auxiliary space.

When to recognize it: The minimum remaining node must be one of two current fronts.

Check before applying it: Reused nodes mutate the input chains; shared nodes or cycles violate the simple ownership contract.

Change one rule

Merge k sorted linked lists.

See what changes

Keep the current front of each nonempty list in a min-heap.

Connect

Two pointers: shrink one search space: Advance one of two monotone frontiers.

Merge sort: combine ordered halves: This merge is the combine step for linked-list merge sort.