A lexer dumps a file’s token kinds into a singly linked list — one node per token, already walked. CI wants a palindrome flag so generated fixtures that were concatenated with their reverse can be tagged. The intern copied every val into an ArrayList and compared from both ends. A unit-test file of a few dozen tokens returned. A generated corpus with tens of thousands of tokens allocated a second list of kinds the lexer had already paid for once.

Palindrome Linked List asks whether the values match from head to tail and from tail to head. You return a boolean. You do not have an index, and you do not have a tail pointer for free.

This is an interview writeup, not a layout lecture. The linked list post owns splice and why get(i) walks. The two pointers post owns slow/fast and opposite-end indexes. The work here is a composition: find a middle, reverse the back half, then compare values pairwise. That last walk is not the zipper in Reorder List.

The problem

Given the head of a singly linked list, return whether the sequence of vals is a palindrome. A one-node list is a palindrome. Empty is not the usual case; if it appears, there is nothing to disagree.

1 → 2 → 2 → 1 → null        →  true
1 → 2 → 3 → 2 → 1 → null    →  true
1 → 2 → 3 → null            →  false
1 → null                    →  true

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: The interview ask is O(1) extra space. Copying values into an array and running opposite-end two pointers is how you would do this on a string — Valid Palindrome already has indexes. A linked list does not. The brute below is correct and still spends O(n) extra space.

Copy the values, compare from both ends

Walk once, store every val in an ArrayList, then meet in the middle the way you would on an array. The answer is right. You paid random access you did not have.

boolean isPalindromeCopy(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) {
        vals.add(n.val);
    }
    int i = 0;
    int j = vals.size() - 1;
    while (i < j) {
        if (!vals.get(i).equals(vals.get(j))) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

At a handful of tokens this is a rounding error. In production you paid O(n) extra space for a question three pointer walks already answer in O(1) besides a few locals: find the middle, reverse the second half, compare until the reversed half ends.

Reverse the second half, then compare

Three steps. None of them is new. The trap is which node you reverse from when the length is odd.

  1. Middle. Paste the loop from Middle of the Linked List. Slow lands on the single middle when the length is odd, and on the second middle when the length is even — the head of the second half.
  2. Skip the middle on odd, then reverse. After that loop, fast == null means even length: reverse from slow. fast != null means odd length: slow sits on the center node, which has no pair — reverse from slow.next. The rewire is the same three pointers Reverse Linked List already taught. Do not re-derive it.
  3. Compare values, not a zipper. Walk head and the new head of the reversed half together. Stop when the reversed half ends. You are reading val, not splicing next. Reorder List uses the same first two ideas and then interleaves; this prompt only asks whether the halves match.

Walk even length 1 → 2 → 2 → 1:

middle (second middle):
  start:  slow=1   fast=1
  step 1: slow=2a  fast=2b
  step 2: slow=2b  fast=null     even — reverse from slow

reverse:  2b → 1 → null     becomes     1 → 2b → null

compare:  1==1,  2a==2b     reversed half ends     →  true

Odd length 1 → 2 → 3 → 2 → 1 skips the center. Reverse from slow here and you would reverse 3 → 2 → 1; comparing until that half ends still works because 3 matches itself. The cleaner split is to leave 3 out of the reverse:

middle:
  start:  slow=1  fast=1
  step 1: slow=2  fast=3
  step 2: slow=3  fast=5     fast.next is null, stop     odd — skip 3

reverse from slow.next:  2 → 1 → null     becomes     1 → 2 → null

compare:  1==1,  2==2     reversed half ends     →  true
          (3 never compared)

You do not need to cut next before the reverse. The first-half tail still points into the second half; the compare stops when the reversed pointer is null, so it never follows that leftover link as a third value. Cutting is required in Reorder List because the zipper would otherwise cycle.

The Java is those three walks. reverse is the sibling rewire.

boolean isPalindrome(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode second = reverse(fast != null ? slow.next : slow);

    ListNode first = head;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    return true;
}

ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Time is O(n) — one walk to the middle, one reverse, one compare; each node is visited a constant number of times. Space is O(1) besides a handful of pointers. The ArrayList copy is also O(n) time and still pays the extra array.

One node: fast.next is null, the middle loop never runs, fast is not null, second is reverse(null), the compare never runs, you return true. Two nodes: one middle step, fast is null, you reverse the second node and compare it to the first. No special cases.

Skip the middle only on odd length. fast == null after the sibling loop means even: slow is the start of the second half. Reverse from slow.next there and you drop the first node of that half — a mismatch that sat in that pair never gets compared, so a non-palindrome can come back true. The list is also mutated; reverse the second half again if a later walker still needs the original order.

What interviewers usually poke next

  • Restore the list. Keep the head of the reversed half, compare, reverse it a second time. Early return false leaves the list half-reversed unless you restore on that path too. Ask whether the caller still owns the original chain.
  • Skip vs self-compare on odd. Reverse from slow on odd length and the middle node compares with itself. Same boolean. The skip is the version that matches “the center has no pair.”
  • Why not Reorder’s middle loop? That loop parks on the first-half tail so you can cut. Palindrome does not zipper, so the second-middle loop plus an odd-length skip is enough. Mixing the two conditions reverses the wrong run.
  • A string / array palindrome. Then opposite-end indexes, no reverse. That is Valid Palindrome, not this job.
  • Recursive outer-in. Recurse to the tail and compare on the way back while a pointer walks forward from head. Correct, O(n) stack — the same extra space as the ArrayList, just on the call stack. Say why the three linear passes are the default.
  • Doubly linked. You already have the tail. Walk inward from both ends. The singly-list bill was that you did not have the tail for free.
  • A cycle in the list. Then fast never hits null. That is Linked List Cycle, not a palindrome walk.

You are done with this problem when you can check 1 → 2 → 3 → 2 → 1 on a whiteboard without an array, and you can say out loud why the middle node is skipped on odd length and why that skip is wrong on even.