3.25 Case Studies

This section combines multiple patterns from the chapter into complete, end-to-end linked list algorithms. Each example highlights how invariants, pointer discipline, and structural operations interact.

Case Study 1: Merge Sort on Linked Lists

Problem

Sort a singly linked list in O(n log n) time using O(1) extra space.

Approach

Use divide-and-conquer:

1. Split the list into two halves
2. Recursively sort each half
3. Merge the sorted halves

Implementation

sort(head):
  if head == null or head.next == null:
    return head

  left, right = split_half(head)

  left = sort(left)
  right = sort(right)

  return merge(left, right)

Key Points

• Splitting uses fast/slow pointers
• Merge uses the sentinel pattern
• Recursion depth is O(log n)

Complexity

Case Study 2: Check Palindrome

Problem

Determine whether a linked list reads the same forward and backward.

Approach

1. Find the middle
2. Reverse the second half
3. Compare both halves

Implementation

is_palindrome(head):
  if head == null or head.next == null:
    return true

  slow = head
  fast = head

  while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next

  second = reverse(slow)
  first = head

  while second != null:
    if first.value != second.value:
      return false
    first = first.next
    second = second.next

  return true

Key Points

• Uses fast/slow pointers
• Uses in-place reversal
• Optional: restore list after check

Complexity

Case Study 3: Partition List Around Pivot

Problem

Reorder a list so that nodes less than x come before nodes greater than or equal to x, preserving order.

Approach

Use two dummy heads.

Implementation

partition(head, x):
  small_dummy = new Node()
  large_dummy = new Node()

  small_tail = small_dummy
  large_tail = large_dummy

  cur = head

  while cur != null:
    next = cur.next
    cur.next = null

    if cur.value < x:
      small_tail.next = cur
      small_tail = cur
    else:
      large_tail.next = cur
      large_tail = cur

    cur = next

  small_tail.next = large_dummy.next
  return small_dummy.next

Key Points

• Stable partition
• Requires detaching nodes
• Uses multiple dummy nodes

Complexity

Case Study 4: Detect and Remove Cycle

Problem

Detect if a cycle exists and remove it.

Approach

1. Use Floyd’s cycle detection
2. Find entry point
3. Break the cycle

Implementation

remove_cycle(head):
  slow = head
  fast = head

  while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
      break

  if fast == null or fast.next == null:
    return head

  ptr1 = head
  ptr2 = slow

  while ptr1 != ptr2:
    ptr1 = ptr1.next
    ptr2 = ptr2.next

  prev = ptr2
  while prev.next != ptr2:
    prev = prev.next

  prev.next = null

  return head

Key Points

• Two-pointer method
• Careful cycle unlinking
• Must preserve list integrity

Complexity

Case Study 5: LRU Cache

Problem

Design a cache with O(1) get and put.

Approach

Combine:

• Hash map for lookup
• Doubly linked list for ordering

Key Operations

get(key):
  node = map[key]
  remove(node)
  insert_front(node)

put(key, value):
  if key exists:
    update and move to front
  else:
    insert new node
    if over capacity:
      remove tail.prev

Key Points

• Requires consistent map + list updates
• Uses sentinel nodes
• Requires O(1) removal and insertion

Complexity

Case Study 6: Reverse in k-Groups

Problem

Reverse nodes in groups of size k.

Approach

Iteratively reverse blocks.

Implementation

reverse_k_group(head, k):
  dummy.next = head
  prev = dummy

  while true:
    kth = prev
    for i in 1..k:
      kth = kth.next
      if kth == null:
        return dummy.next

    group_end = kth.next

    cur = prev.next
    prev_sub = group_end

    while cur != group_end:
      next = cur.next
      cur.next = prev_sub
      prev_sub = cur
      cur = next

    temp = prev.next
    prev.next = kth
    prev = temp

Key Points

• Combines reversal and splitting
• Requires careful boundary control
• Uses dummy node

Complexity

Common Patterns Across Cases

Key Insight

Complex linked list problems are compositions of a small set of primitives:

• traverse
• split
• merge
• reverse
• insert
• delete

Mastery comes from combining these primitives while preserving invariants and reachability. Each case study is a controlled composition of these building blocks.