Split a Java linked chain into two halves without copying nodes

Last updated: 1 Oct 20264 min read

tutorial

A slow and a fast cursor can split an acyclic linked chain into a left half and a right half by clearing one next link.

Choose where the odd node belongs

Start the fast cursor one link ahead of the slow cursor. When the fast cursor reaches the end, slow is the final node of the left half. For odd lengths, the left half gets the extra node. Save slow.next as the right root, then set slow.next to null to make two independent chains.

For an empty chain, return two null roots. For one node, return that node on the left and null on the right. These cases must be explicit before dereferencing head.next.

Treat split as a mutation

The original head now reaches only the left half. A caller that needs both must retain the returned pair. This is the same cut required by linked merge sort before recursing. Without it, recursion can revisit the same nodes indefinitely.

The method assumes no cycle and no concurrent traversal. If another root shares a suffix, splitting can alter that root's traversal too; check intersection by identity when ownership is uncertain.

Working program

public class SplitDispatchChain {
    static final class Node {
        final String dispatchId;
        Node next;
        Node(String dispatchId, Node next) { this.dispatchId = dispatchId; this.next = next; }
    }
    static Node[] split(Node head) {
        if (head == null) return new Node[] {null, null};
        Node slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node right = slow.next;
        slow.next = null;
        return new Node[] {head, right};
    }
    static String labels(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node cursor = head; cursor != null; cursor = cursor.next) {
            if (result.length() > 0) result.append(",");
            result.append(cursor.dispatchId);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Node head = new Node("load-15", new Node("scan-47", new Node("seal-82",
            new Node("pack-20", new Node("ship-35", null)))));
        Node[] halves = split(head);
        System.out.println(labels(halves[0]));
        System.out.println(labels(halves[1]));
        System.out.println(split(null)[1] == null);
    }
}

Output

load-15,scan-47,seal-82
pack-20,ship-35
true

Cost and ownership

The two-cursor walk takes O(n) time and O(1) cursor space; the returned two-element array is a fixed allocation. No Node or payload is copied, and both returned roots own existing links.

Common Mistakes

Do not forget the cut at slow.next.
Do not dereference head.next before handling an empty input.
Do not assume both halves have equal length for odd-sized chains.