Linked List Merge & Sort Techniques

Merging and sorting are the two most important operations on sorted linked lists. Unlike arrays where you need O(n) extra space for merge sort, linked lists can be merged in-place — making merge sort the ideal sorting algorithm for them.

Merge Two Sorted Linked Lists

This is the fundamental building block. Given two sorted lists, combine them into one sorted list.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def merge_two_sorted(l1, l2):
    """
    Merge two sorted linked lists into one sorted list.
    Time: O(m + n), Space: O(1) — only pointer changes
    """
    dummy = ListNode(0)  # Dummy node avoids edge cases
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    # Attach whichever list has remaining nodes
    tail.next = l1 if l1 else l2

    return dummy.next

Why the dummy node?

Without a dummy node, you need special-case code to determine which node becomes the head of the merged list. The dummy node lets you always append to tail.next, then return dummy.next as the real head.

Tracing through an example

l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6

Step 1: 1 < 2  → pick 1   → merged: 1
Step 2: 3 > 2  → pick 2   → merged: 1 -> 2
Step 3: 3 < 4  → pick 3   → merged: 1 -> 2 -> 3
Step 4: 5 > 4  → pick 4   → merged: 1 -> 2 -> 3 -> 4
Step 5: 5 < 6  → pick 5   → merged: 1 -> 2 -> 3 -> 4 -> 5
Remaining: 6   → attach    → merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Recursive version

def merge_two_sorted_recursive(l1, l2):
    """
    Merge two sorted lists recursively.
    Time: O(m + n), Space: O(m + n) — call stack
    """
    if not l1:
        return l2
    if not l2:
        return l1

    if l1.val <= l2.val:
        l1.next = merge_two_sorted_recursive(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_sorted_recursive(l1, l2.next)
        return l2

The iterative version is preferred in practice due to O(1) space.

Finding the Middle of a Linked List

Before we can do merge sort, we need to split the list in half. The slow/fast pointer technique finds the middle in one pass:

def find_middle(head):
    """
    Find the middle node (left-middle for even-length lists).
    Time: O(n), Space: O(1)
    """
    slow = head
    fast = head

    # Stop when fast reaches end
    # For even-length, slow lands on left-middle
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    return slow  # This is the middle (or left-middle)

Why fast.next and fast.next.next instead of fast and fast.next? The first version stops slow at the left middle for even-length lists, which is what we need for splitting — we want to cut at mid.next = None.

# Example: 1 -> 2 -> 3 -> 4 -> 5 -> 6
# slow stops at 3 (left middle)
# We split: [1,2,3] and [4,5,6]

Merge Sort on Linked Lists

Merge sort is the best sorting algorithm for linked lists because:

1. No random access needed: Merge sort only needs sequential access
2. O(1) extra space for merging: We just rearrange pointers
3. Stable sort: Equal elements maintain their relative order
4. O(n log n) guaranteed: Unlike quicksort, no worst case

def merge_sort_ll(head):
    """
    Sort a linked list using merge sort.
    Time: O(n log n), Space: O(log n) — recursive stack
    """
    # Base case: empty or single node
    if not head or not head.next:
        return head

    # Step 1: Find the middle
    mid = find_middle(head)
    right_head = mid.next
    mid.next = None  # Cut the list in half

    # Step 2: Recursively sort both halves
    left = merge_sort_ll(head)
    right = merge_sort_ll(right_head)

    # Step 3: Merge the sorted halves
    return merge_two_sorted(left, right)

Why O(log n) space?

The only extra space is the recursion stack. Each recursive call splits the list in half, giving O(log n) levels of recursion. The merge step itself is O(1) space since we rearrange existing nodes.

Complete test

def from_list(arr):
    dummy = ListNode(0)
    curr = dummy
    for v in arr:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next

def to_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


# Test merge sort
import random
arr = random.sample(range(1, 101), 20)  # 20 random numbers
print(f"Before: {arr}")

head = from_list(arr)
sorted_head = merge_sort_ll(head)
result = to_list(sorted_head)
print(f"After:  {result}")
assert result == sorted(arr), "Sort failed!"
print("Merge sort works correctly!")

Bottom-Up Merge Sort (Iterative)

The recursive version uses O(log n) stack space. We can make it fully iterative:

def merge_sort_bottom_up(head):
    """
    Bottom-up merge sort — fully iterative.
    Time: O(n log n), Space: O(1)
    """
    if not head or not head.next:
        return head

    # Get the length
    length = 0
    node = head
    while node:
        length += 1
        node = node.next

    dummy = ListNode(0)
    dummy.next = head
    size = 1  # Start with sublists of size 1

    while size < length:
        tail = dummy
        curr = dummy.next

        while curr:
            # Split off a sublist of `size` nodes
            left = curr
            right = split(left, size)
            curr = split(right, size)

            # Merge left and right, append to tail
            merged_head, merged_tail = merge_and_return_tail(left, right)
            tail.next = merged_head
            tail = merged_tail

        size *= 2

    return dummy.next


def split(head, size):
    """Split off `size` nodes from head, return the start of the rest."""
    for _ in range(size - 1):
        if not head:
            break
        head = head.next

    if not head:
        return None

    rest = head.next
    head.next = None
    return rest


def merge_and_return_tail(l1, l2):
    """Merge two sorted lists, return (head, tail) of merged list."""
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    while tail.next:
        tail = tail.next

    return dummy.next, tail

Merge K Sorted Linked Lists

Given K sorted linked lists, merge them all into one sorted list. This is a classic interview problem with multiple approaches.

Approach 1: Merge pairs iteratively — O(N log K)

def merge_k_sorted_pairwise(lists):
    """
    Merge K sorted lists by repeatedly merging pairs.
    Time: O(N log K) where N = total nodes
    Space: O(1)
    """
    if not lists:
        return None

    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two_sorted(l1, l2))
        lists = merged

    return lists[0]

Approach 2: Min-heap — O(N log K)

import heapq

def merge_k_sorted_heap(lists):
    """
    Merge K sorted lists using a min-heap.
    Time: O(N log K), Space: O(K) — heap size
    """
    dummy = ListNode(0)
    tail = dummy

    # Initialize heap with the head of each list
    # heapq needs comparable items — use (value, index) to break ties
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))

    while heap:
        val, idx, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next

        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))

    return dummy.next

Why use the index in the heap tuple?

Python’s heapq compares tuples element by element. If two nodes have the same value, it tries to compare the ListNode objects, which raises a TypeError. The index serves as a tiebreaker.

Approach 3: Divide and conquer — O(N log K)

def merge_k_sorted_dc(lists):
    """
    Merge K sorted lists using divide and conquer.
    Time: O(N log K), Space: O(log K) — recursion
    """
    if not lists:
        return None
    return merge_range(lists, 0, len(lists) - 1)

def merge_range(lists, start, end):
    if start == end:
        return lists[start]
    mid = (start + end) // 2
    left = merge_range(lists, start, mid)
    right = merge_range(lists, mid + 1, end)
    return merge_two_sorted(left, right)

Comparing the approaches

Approach	Time	Space	Notes
Merge one by one	O(NK)	O(1)	Too slow
Pairwise merging	O(N log K)	O(1)	Simple, efficient
Min-heap	O(N log K)	O(K)	Best when K is large
Divide & conquer	O(N log K)	O(log K)	Elegant recursive

All three efficient approaches are O(N log K). The heap approach is most intuitive in interviews.

Insertion Sort on Linked Lists

For nearly-sorted lists, insertion sort can be efficient:

def insertion_sort_list(head):
    """
    Insertion sort on a linked list.
    Time: O(n^2) worst, O(n) if nearly sorted
    Space: O(1)
    """
    dummy = ListNode(0)
    curr = head

    while curr:
        nxt = curr.next

        # Find insertion position in sorted portion
        prev = dummy
        while prev.next and prev.next.val < curr.val:
            prev = prev.next

        # Insert curr after prev
        curr.next = prev.next
        prev.next = curr

        curr = nxt

    return dummy.next

Why Merge Sort Beats Quicksort for Linked Lists

Factor	Merge Sort	Quicksort
Random access needed?	No	Yes (partition step)
Merge cost	O(1) extra space	O(1) extra space
Split cost	O(n) — find middle	O(n) — partition
Worst case	O(n log n) always	O(n^2)
Cache performance	Irrelevant for LL	Irrelevant for LL

For arrays, quicksort wins because of cache locality. For linked lists, that advantage disappears, and merge sort’s guaranteed O(n log n) makes it the clear winner.

Complexity Summary

Algorithm	Time	Space
Merge two sorted lists	O(m + n)	O(1)
Find middle	O(n)	O(1)
Merge sort (recursive)	O(n log n)	O(log n)
Merge sort (bottom-up)	O(n log n)	O(1)
Merge K sorted lists	O(N log K)	O(K) heap
Insertion sort	O(n^2)	O(1)

Practice Problems

1. LeetCode 21 — Merge Two Sorted Lists: The fundamental merge operation (Easy)
2. LeetCode 23 — Merge k Sorted Lists: Heap or divide-and-conquer approach (Hard)
3. LeetCode 148 — Sort List: Merge sort on a linked list (Medium)
4. LeetCode 147 — Insertion Sort List: Insertion sort variant (Medium)
5. LeetCode 876 — Middle of the Linked List: Slow/fast pointer (Easy)
6. LeetCode 86 — Partition List: Partition around a value, then merge (Medium)

Key Takeaways

• The dummy node pattern is essential for merging — it eliminates all head-pointer edge cases.
• Merge sort is the ideal sorting algorithm for linked lists: O(n log n) time, O(1) merge space, stable, guaranteed.
• For merging K lists, use a min-heap for O(N log K) time — each node enters and exits the heap exactly once.
• The slow/fast pointer technique for finding the middle is a prerequisite for merge sort on linked lists.