IntermediateLinked Lists

Merge/Split Lists

Merge multiple sorted lists, sort a list, or partition around a value

Time: O(n log k)
Space: O(1)–O(log n)
Pattern Overview

Core Idea

Use dummy heads and pointer weaving; for k-way merges use a heap; for sort use merge sort on list.

When to Use

Use for merging k sorted lists, sorting a list in O(n log n), or partitioning relative to a pivot.

General Recognition Cues
General indicators that this pattern might be applicable
  • Merge k lists
  • List sort
  • Partition around x
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Merge k Lists

Min-heap of list heads or divide & conquer

When to Use This Variant
  • k sorted inputs
Use Case
Global sorted output
Advantages
  • O(n log k)
  • Simple with heap
Implementation
import heapq
def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node: heapq.heappush(heap, (node.val, i, node))
    dummy = ListNode(0)
    cur = dummy
    while heap:
        _, i, node = heapq.heappop(heap)
        cur.next = node; cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next
2

Sort List

Top-down or bottom-up merge sort on list

When to Use This Variant
  • O(n log n) in-place
Use Case
Stable sort
Advantages
  • No extra arrays
  • Deterministic
Implementation
def sort_list(head):
    if not head or not head.next: return head
    # split
    slow, fast = head, head.next
    while fast and fast.next: slow = slow.next; fast = fast.next.next
    mid = slow.next; slow.next = None
    # merge
    left = sort_list(head); right = sort_list(mid)
    return merge(left, right)
def merge(a, b):
    dummy = ListNode(0); cur = dummy
    while a and b:
        if a.val < b.val: cur.next, a = a, a.next
        else: cur.next, b = b, b.next
        cur = cur.next
    cur.next = a or b
    return dummy.next
3

Partition Around Value

Stable partition using two chains

When to Use This Variant
  • < x then ≥ x
Use Case
Reordering
Advantages
  • O(n) time
  • O(1) space
Implementation
def partition_list(head, x):
    before = ListNode(0); after = ListNode(0)
    b, a = before, after
    cur = head
    while cur:
        if cur.val < x:
            b.next = cur; b = b.next
        else:
            a.next = cur; a = a.next
        cur = cur.next
    a.next = None; b.next = after.next
    return before.next
Common Pitfalls
Watch out for these common mistakes
  • Forgetting to terminate tails
  • Cycle creation on bad links
  • Heap vs divide & conquer tradeoff
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n log k)

Heap/divide & conquer costs.

Space Complexity
O(1)–O(log n)

Pointers; recursion costs log n.

Ready to test your knowledge?

Test your pattern recognition with interactive questions