☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Check if LL is palindrome or not

Medium TUF ID 2844 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Return true if the sequence of values reads the same from front to back as from back to front, and false otherwise. An empty list and a single node are palindromes. The list should be left exactly as it was when the function returns.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer. The follow-up asks for O(n) time and O(1) extra space.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

head = 1 -> 2 -> 2 -> 1
answer = true                 // pairs (1,1) and (2,2) match

Example 2

head = 1 -> 2 -> 3 -> 2 -> 1
answer = true                 // odd length: the middle 3 pairs with itself

Example 3

head = 1 -> 2
answer = false                // 1 != 2

Approach 1: Brute force, copy to a stack

Intuition. A singly linked list can only be read forwards. If we copy all the values onto a stack, popping them gives the values backwards. Walk the list a second time and compare each node’s value with the popped value; the first mismatch proves the list is not a palindrome.

Algorithm.

  1. Walk from head and push every value onto a stack.
  2. Walk from head again. For each node, pop the stack; if the values differ, return false.
  3. Return true when the second walk finishes.
static boolean bruteForce(ListNode head) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (ListNode t = head; t != null; t = t.next) stack.push(t.val);
    for (ListNode t = head; t != null; t = t.next) {
        if (t.val != stack.pop()) return false;   // the pop yields the values back to front
    }
    return true;
}

Complexity. Time O(n): two passes with constant work per node. Space O(n): the stack holds all n values.

Copying into an ArrayList and comparing with two indices from both ends is an equivalent alternative. Both are fine answers, but the interesting part of the problem is doing it without a copy.

Approach 2: Optimal, reverse the second half in place

Intuition. A palindrome’s second half is the mirror image of its first half. We cannot read the second half backwards directly, but we can reverse it in place and then read it forwards, which is the same thing. So: find the middle, reverse the part after the middle, and walk the two halves together comparing values. Afterwards, reverse the second half again so the caller’s list is unchanged.

The middle is found with slow and fast pointers. We want slow to stop on the last node of the first half, so that slow.next is the first node of the second half. Using the condition fast.next != null && fast.next.next != null achieves exactly that: for an even length 2k, slow ends on node k; for an odd length 2k + 1, slow ends on the middle node k + 1, which is then left out of the comparison (a middle element always matches itself).

Algorithm.

  1. If the list has fewer than two nodes, return true.
  2. Set slow = head, fast = head. While fast.next and fast.next.next are non-null, move slow by one and fast by two.
  3. Let secondHalf = reverse(slow.next).
  4. Walk a from head and b from secondHalf while b is non-null; if a.val != b.val, note the failure and stop.
  5. Restore: slow.next = reverse(secondHalf).
  6. Return the result of the comparison.
static boolean optimal(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {   // slow stops on the last node of the first half
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode secondHalf = reverse(slow.next);              // second half, now reversed
    boolean palindrome = true;
    ListNode a = head, b = secondHalf;
    while (b != null) {                                     // the second half is never longer than the first
        if (a.val != b.val) { palindrome = false; break; }
        a = a.next;
        b = b.next;
    }
    slow.next = reverse(secondHalf);                        // put the list back the way it was
    return palindrome;
}

The reversal is the standard three-pointer routine:

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

Dry run on 1 -> 2 -> 2 -> 1:

step state
find middle slow stops on the second node (value 2); fast on the third
reverse second half 2 -> 1 becomes 1 -> 2; secondHalf is the old tail
compare a=1, b=1 ok; a=2, b=2 ok; b becomes null, stop
restore 1 -> 2 reversed back to 2 -> 1 and reattached after slow
result true

On 1 -> 2 -> 3 -> 2 -> 1, slow stops on the 3; the second half 2 -> 1 is reversed to 1 -> 2 and compared against 1 -> 2 from the head. The 3 is never compared, which is correct.

Complexity. Time O(n): finding the middle, reversing, comparing and restoring are each a single pass over at most n nodes. Space O(1): a handful of pointers; nothing is copied.

The Java test checks, after every call to optimal, that toArray(head) still equals the original input and that calling optimal a second time on the restored list gives the same answer. This matters most in the early-exit case (2 -> 1 -> 1 -> 2 -> 1), where the comparison stops after the first mismatch but the restoration must still happen.

Edge cases and pitfalls