Palindrome Linked List

Description

Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Brute Force Approach: Copy to ArrayList

Intuition: Copy all node values into an ArrayList so you can traverse backward from the end using standard array two-pointers.

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode curr = head;
 
        // 1. Copy elements to list
        while (curr != null) {
            list.add(curr.val);
            curr = curr.next;
        }
 
        // 2. Compare from both ends moving inward
        int left = 0, right = list.size() - 1;
        while (left < right) {
            if (!list.get(left).equals(list.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
 

• Time Complexity: $O(n)$ — requires traversing all nodes once to populate the list and once to compare.
• Space Complexity: $O(n)$ — requires extra space to store $n$ node values.

---

Optimized Approach: Fast & Slow Pointers (Inline)

Intuition: Solve 234. Palindrome Linked List in $O(1)$ extra space by executing three clean passes directly in the main function: finding the middle, reversing the second half, and comparing the ends.

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
 
        // 1. Find middle (slow pointer stops at the midpoint)
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
 
        // 2. Reverse second half inline
        ListNode prev = null;
        while (slow != null) {
            ListNode tmp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = tmp;
        }
 
        // 3. Check palindrome from left head and right head (prev)
        ListNode left = head, right = prev;
        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
 
        return true;
    }
}
 

• Time Complexity: $O(n)$ — scans through half the list for middle discovery, half for reversal, and half for checking.
• Space Complexity: $O(1)$ — modifies pointer directions in-place without creating new data structures.