Topics › Linked List › Medium Problems of LL

Check if LL is palindrome or not

Medium TUF ID 618 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given the head of a singly linked list of integers, 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 one-node list are palindromes.

The difficulty is that a singly linked list can only be walked forwards. With an array you would compare a[i] with a[n - 1 - i]; here there is no cheap way to reach “the i-th node from the end”.

Constraints: 1 ≤ n ≤ 10^5 nodes (we also accept an empty list), values 0 ≤ val ≤ 9 in the LeetCode version. 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; }
}

Example 1

head = 1 -> 2 -> 2 -> 1
answer = true          // reversed, it is still 1 2 2 1

Example 2

head = 1 -> 2
answer = false         // reversed it is 2 1

Example 3

head = 1 -> 2 -> 3 -> 2 -> 1
answer = true          // odd length: the middle value 3 is compared with nothing

Approach 1: Brute force, use a stack to read the list backwards

Intuition. A palindrome is a sequence equal to its own reverse. We cannot walk the list backwards, but a stack hands back values in reverse order of insertion. Push every value while walking forwards; then walk forwards again and compare each node with the value popped from the stack. The first pop is the last value of the list, the second pop is the second-to-last value, and so on, which is exactly the “mirror” comparison we need.

Algorithm.

1. Walk the list and push each value onto a stack.
2. Walk the list again. For each node, pop a value and compare. On a mismatch, return false.
3. If every pair matched, return true.

static boolean bruteForce(ListNode head) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (ListNode cur = head; cur != null; cur = cur.next) stack.push(cur.val);
    for (ListNode cur = head; cur != null; cur = cur.next) {
        if (cur.val != stack.pop()) return false;   // pop() yields the values from the back
    }
    return true;
}

Complexity. Time O(n): two passes. Space O(n): the stack holds every value.

A small improvement is to stop the second walk after n / 2 nodes, since the second half only repeats comparisons already made. It halves the comparisons but not the memory, so it does not change the picture.

A subtle Java detail: stack.pop() returns an Integer. The expression cur.val != stack.pop() unboxes it because cur.val is a primitive int, so this is a numeric comparison. Comparing two Integer objects with != would compare references, which happens to work for values from -128 to 127 (they are cached) and silently fails for larger ones. The Java tests include values like 1000 to guard against that mistake.

Approach 2: Optimal, reverse the second half in place

Intuition. The stack exists only to give us the second half in reverse order. We can get that for free by actually reversing the second half of the list, then walking the first half and the reversed second half side by side. Three ingredients:

1. Find the middle with slow and fast pointers. With the loop condition fast.next != null && fast.next.next != null, slow stops on the last node of the first half: node n/2 (1-based) for even n, the exact middle for odd n.
2. Reverse the part after slow. Now secondHalf starts at the old last node.
3. Compare from head and from secondHalf until secondHalf runs out. For odd n the first half is one node longer (it includes the middle), and the middle is never compared, which is correct because it mirrors itself.

Finally, reverse the second half again and reattach it. A function called isPalindrome should not leave the caller’s list scrambled.

Algorithm.

1. If the list has zero or one node, return true.
2. Move slow by one and fast by two while fast.next and fast.next.next exist.
3. secondHalf = reverse(slow.next).
4. Walk p from head and q from secondHalf while q != null; on the first mismatch record false and stop.
5. Restore: slow.next = reverse(secondHalf). Return the recorded result.

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 = slow.next;                           // slow stops at the last node of the first half
        fast = fast.next.next;
    }
    ListNode secondHalf = reverse(slow.next);
    boolean isPalindrome = true;
    for (ListNode p = head, q = secondHalf; q != null; p = p.next, q = q.next) {
        if (p.val != q.val) {
            isPalindrome = false;
            break;
        }
    }
    slow.next = reverse(secondHalf);                // put the list back the way the caller gave it
    return isPalindrome;
}

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

Dry run on Example 3 (1 2 3 2 1, indices 0 to 4):

The second half is 2 -> 1, reversed to 1 -> 2. Comparisons: 1 vs 1, then 2 vs 2, then q becomes null. Result true. The middle 3 was never compared. Reversing 1 -> 2 back to 2 -> 1 and attaching it after node 3 restores the original list.

For Example 1 (1 2 2 1), slow stops at index 1 because after the first move fast is at index 2 and fast.next.next is null. The second half 2 -> 1 reverses to 1 -> 2, and both comparisons succeed.

Complexity. Time O(n): about n / 2 steps to find the middle, n / 2 to reverse, at most n / 2 to compare, and n / 2 to restore. Space O(1): only pointers.

Edge cases and pitfalls

• Empty and single-node lists. Both are palindromes. The early return in optimal avoids dereferencing head.next on an empty list.
• Even vs odd length. With the loop condition above, slow always ends on the last node of the first half, so one code path handles both. Using fast != null && fast.next != null instead puts slow on the second middle for even n, and you would then have to reverse from slow rather than slow.next. Either convention works if applied consistently.
• Forgetting to restore. Returning early from inside the comparison loop would skip the restore step. That is why the method records the result in a flag, breaks, and always reverses back before returning. The Java tests check that the list is unchanged after the call.
• Concurrent readers. While the method runs, the list is temporarily modified. If another thread could read the list at the same time, use the stack approach instead.
• Boxed comparison. As noted above, compare an int with an Integer, or two ints, never two Integer objects with == or !=.
• Long lists. A recursive solution (comparing a “front” pointer with nodes as the recursion unwinds) also works but uses O(n) call stack and can overflow at 10^5 nodes. The tests run both methods on a list of 100 001 nodes.

Related problems

• Check if LL is palindrome or not is the same problem in the A2Z sheet.
• Reverse a LL is the reversal routine used twice here.
• Find Middle of Linked List explains the slow and fast pointer technique used to split the list.
• Check if String is Palindrome or Not is the array version, where two indices can walk towards each other.