# 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

```text id="ms1"
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

| Metric | Value          |
| ------ | -------------- |
| Time   | O(n log n)     |
| Space  | O(log n) stack |
## 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

```text id="ms2"
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

| Metric | Value |
| ------ | ----- |
| Time   | O(n)  |
| Space  | O(1)  |
## 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

```text id="ms3"
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

| Metric | Value |
| ------ | ----- |
| Time   | O(n)  |
| Space  | O(1)  |
## 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

```text id="ms4"
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

| Metric | Value |
| ------ | ----- |
| Time   | O(n)  |
| Space  | O(1)  |
## 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

```text id="ms5"
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

| Metric | Value        |
| ------ | ------------ |
| Time   | O(1) average |
| Space  | O(capacity)  |
## Case Study 6: Reverse in k-Groups

### Problem

Reverse nodes in groups of size k.

### Approach

Iteratively reverse blocks.

### Implementation

```text id="ms6"
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

| Metric | Value |
| ------ | ----- |
| Time   | O(n)  |
| Space  | O(1)  |
## Common Patterns Across Cases

| Pattern               | Used In                            |
| --------------------- | ---------------------------------- |
| Dummy nodes           | partition, deletion, k-group       |
| Fast/slow pointers    | palindrome, cycle detection, split |
| Reversal              | palindrome, k-group                |
| Merge                 | merge sort                         |
| Two lists             | partition, merge                   |
| Structural invariants | all                                |
## 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.