3.8 Split Patterns

Splitting a linked list means cutting one list into two or more lists while preserving the original nodes. The operation changes links, not values. It appears in merge sort, partitioning, alternating lists, palindrome checks, and algorithms that process the front and back halves separately.

Problem

Given the head of a singly linked list, divide it into parts according to a rule.

Common rules include:

split into first half and second half
split after k nodes
split by predicate
split into alternating nodes

The main danger is losing a suffix by overwriting a next pointer before saving it.

Split After k Nodes

To split after exactly k nodes, walk to the kth node and cut the edge after it.

if head == null:
  return (null, null)

cur = head

for i in 1..k-1:
  if cur.next == null:
    return (head, null)
  cur = cur.next

second = cur.next
cur.next = null

return (head, second)

For:

a -> b -> c -> d -> e -> null

with k = 3, the result is:

first:  a -> b -> c -> null
second: d -> e -> null

The invariant is that cur always points to the last node of the first part constructed so far. The final assignment cur.next = null makes the first part a complete list.

Split into Two Halves

Use the first-middle convention when the first half should have the same length as the second half, or one extra node when the length is odd.

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

slow = head
fast = head.next

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

second = slow.next
slow.next = null

return (head, second)

For an even-length list:

a -> b -> c -> d -> null

the result is:

first:  a -> b -> null
second: c -> d -> null

For an odd-length list:

a -> b -> c -> d -> e -> null

the result is:

first:  a -> b -> c -> null
second: d -> e -> null

This form is useful for merge sort because it guarantees progress: both halves are smaller than the original list when the length is at least two.

Split by Predicate

Sometimes each node should be placed into one of two output lists depending on its value.

yes_dummy = new Node()
no_dummy = new Node()

yes_tail = yes_dummy
no_tail = no_dummy

cur = head

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

  if predicate(cur.value):
    yes_tail.next = cur
    yes_tail = cur
  else:
    no_tail.next = cur
    no_tail = cur

  cur = next

return (yes_dummy.next, no_dummy.next)

The assignment cur.next = null is important. It detaches the current node from the original list before appending it to a new list. Without this step, one output list may accidentally retain a chain of nodes that belong to the other output list.

Stable Partition

A predicate split is stable if nodes retain their original relative order inside each output list. The previous algorithm is stable because it appends nodes to the tail of each output list.

Example:

3 -> 1 -> 4 -> 2 -> 5 -> null

Split by value < 3:

yes: 1 -> 2 -> null
no:  3 -> 4 -> 5 -> null

The nodes in each list appear in the same order as in the input.

Alternating Split

An alternating split sends nodes at positions 1, 3, 5, … to the first list and nodes at positions 2, 4, 6, … to the second list.

a_dummy = new Node()
b_dummy = new Node()

a_tail = a_dummy
b_tail = b_dummy

cur = head
take_a = true

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

  if take_a:
    a_tail.next = cur
    a_tail = cur
  else:
    b_tail.next = cur
    b_tail = cur

  take_a = not take_a
  cur = next

return (a_dummy.next, b_dummy.next)

For:

a -> b -> c -> d -> e -> null

the result is:

first:  a -> c -> e -> null
second: b -> d -> null

This pattern is useful when distributing work across two passes or when implementing some recursive list algorithms.

Split Around a Pivot

Partition a list into nodes smaller than a pivot and nodes greater than or equal to a pivot.

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 < pivot:
    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

This is the linked-list analogue of array partitioning, but it avoids swaps. Nodes are moved by relinking.

Splitting for Merge Sort

Merge sort on linked lists begins by splitting the list into halves.

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)

The split must physically cut the list. If slow.next = null is omitted, recursive calls may continue seeing the original full list, causing infinite recursion.

Complexity Summary

Common Failure Modes

The most common error is overwriting a link before saving the suffix. In any loop that moves nodes into another list, write:

next = cur.next
cur.next = null

before appending cur.

Another error is failing to cut the first list when splitting into halves. If second = slow.next is saved but slow.next = null is omitted, both results still share structure.

A third error is returning the sentinel node instead of the first real node. The correct return value is usually dummy.next.

Key Insight

Splitting is controlled separation. The algorithm must preserve reachability while deciding where each node belongs. A safe split follows three steps: save the suffix, detach the current edge, and attach the node or segment to its new owner.