Check a Java linked palindrome and restore the original links

Last updated: 1 Oct 20264 min read

tutorial

A linked-chain palindrome check compares the first half with a reversed second half, then reverses that half again before returning.

Treat temporary mutation as an obligation

A slow pointer locates the middle while a fast pointer advances twice as quickly. For odd lengths, the middle node is excluded from comparison. Reverse the second half, compare corresponding IDs, and restore the same links in a finally block even when a mismatch returns early. The fixture checks both an odd palindrome and a non-palindrome, then prints the latter chain to prove its links were restored.

The algorithm assumes an acyclic chain and exclusive access while it runs. During comparison, the second half is temporarily pointed backward; another reader could see a truncated or malformed path. Cycle detection and an ownership rule belong before this method in a shared structure.

Keep the comparison contract small

The code compares non-null dispatch IDs by String.equals. Null identifiers are rejected at node construction in a real domain model; this fixture uses literal IDs to keep the link algorithm visible. If equality means case folding or Unicode normalization, perform that policy at input rather than quietly changing the palindrome relation here.

A java.util.LinkedList offers a descending iterator, but it does not expose internal nodes for half reversal. A two-iterator comparison can be simpler when O(1) extra space is not an interview constraint. Reverse traversal documents that API route.

Working program

public class DispatchPalindromeCheck {
    static final class Node {
        final String dispatchId;
        Node next;
        Node(String dispatchId, Node next) { this.dispatchId = dispatchId; this.next = next; }
    }
    static Node reverse(Node head) {
        Node previous = null;
        for (Node current = head; current != null; ) {
            Node following = current.next;
            current.next = previous;
            previous = current;
            current = following;
        }
        return previous;
    }
    static boolean isPalindrome(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node secondHalf = fast == null ? slow : slow.next;
        Node reversed = reverse(secondHalf);
        try {
            Node left = head, right = reversed;
            while (right != null) {
                if (!left.dispatchId.equals(right.dispatchId)) return false;
                left = left.next; right = right.next;
            }
            return true;
        } finally {
            reverse(reversed);
        }
    }
    static String labels(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node current = head; current != null; current = current.next) {
            if (result.length() > 0) result.append(",");
            result.append(current.dispatchId);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Node matching = new Node("scan", new Node("seal", new Node("scan", null)));
        Node different = new Node("scan", new Node("seal", new Node("ship", null)));
        System.out.println(isPalindrome(matching));
        System.out.println(isPalindrome(different));
        System.out.println(labels(different));
        System.out.println(isPalindrome(null));
    }
}

Output

true
false
scan,seal,ship
true

Cost and ownership

The middle scan, half reversal, comparison, and restoration together take O(n) time and O(1) auxiliary node references. The method mutates links temporarily; it is unsuitable for unsynchronized shared reads even though the final visible chain is restored.

Common Mistakes

Do not forget the restore step on a mismatch.
Do not compare the middle node against itself for odd lengths.
Do not run this algorithm on a cyclic or concurrently traversed chain.

Continue with owned-node algorithms

Continue with Split a Java linked chain into two halves without copying nodes, Test Java linked-chain mutations with node-identity invariants.

java

linked-palindrome-restore