Rotate a singly linked chain right by k positions in Java

Reduce the shift before changing links

Measure the chain length and retain its tail. A shift by the length, or any multiple of it, changes nothing, so use k modulo length. For a nonzero remainder, the new tail is length minus remainder minus one links from the old head. Join the old tail to the old head only after those positions are known, then cut the new tail's next link.

Reject negative shifts as a separate contract rather than silently interpreting them as left rotations. Empty and single-node chains return unchanged. This avoids division by zero and unnecessary temporary cycles.

Publish the returned root

Rotation changes which node is first. The caller must replace its root with the returned reference; an alias to the old head now points into the middle. This is the same root-ownership issue as reversal, though neither operation copies payloads.

A cycle in the input would make length measurement nonterminating. Use cycle detection if acyclicity is not established when building the chain.

Working program

public class RotateDispatchChain {
    static final class Node {
        final String dispatchId;
        Node next;
        Node(String dispatchId, Node next) { this.dispatchId = dispatchId; this.next = next; }
    }
    static Node rotateRight(Node head, int positions) {
        if (positions < 0) throw new IllegalArgumentException("negative rotation");
        if (head == null || head.next == null) return head;
        int length = 1;
        Node tail = head;
        while (tail.next != null) { tail = tail.next; length++; }
        int shift = positions % length;
        if (shift == 0) return head;
        Node newTail = head;
        for (int step = 1; step < length - shift; step++) newTail = newTail.next;
        Node newHead = newTail.next;
        tail.next = head;
        newTail.next = null;
        return newHead;
    }
    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("seal-47", new Node("ship-82", null)));
        System.out.println(labels(rotateRight(head, 5)));
        System.out.println(rotateRight(null, 47) == null);
    }
}

Output

seal-47,ship-82,load-15
true

Cost and ownership

Length measurement and the split walk take O(n) time with O(1) extra references. The temporary cycle exists only between two assignments within this method; concurrent traversal or exceptions inserted between them would require a stronger synchronization design.

Common Mistakes

• Do not connect tail to head before determining the cut point.
• Do not use the old head after publishing the rotated root.
• Do not calculate modulo length when the chain is empty.

Read next

Reverse a singly linked chain in Java without allocating new nodes, linked middle split, Find the entry of a cycle in a Java singly linked chain, linked reverse k group.