1. Traverse the linked list and copy every node's value into an array.
2. Use the standard two-pointer technique on the array: initialize one pointer at the start and one at the end.
3. Move the pointers toward the center, checking if values match at each step.

Pseudo-code:

text
function isPalindrome(head):
    values = []
    current = head
    while current is not null:
        values.append(current.val)
        current = current.next
    
    left = 0
    right = values.length - 1
    while left < right:
        if values[left] != values[right]:
            return false
        left++
        right--
    return true

Complexity Analysis:

• Time Complexity: $O(N)$, where $N$ is the number of nodes. We traverse the list once to copy values and iterate over the array once.
• Space Complexity: $O(N)$ to store the array of values.

Why it fails: While this solution is correct and passes basic test cases, it requires $O(N)$ extra memory. In an interview context, the constraint or follow-up question often specifically requests an $O(1)$ space complexity solution. The brute force approach fails to meet this memory optimization requirement.

Core Insight for Palindrome Linked List

The core difficulty in LeetCode 234 is accessing the tail of the list and moving backwards while simultaneously moving forwards from the head.

To solve this without extra space, we can logically split the list into two halves. If the list is a palindrome, the first half must be identical to the reverse of the second half.

The algorithm relies on three main steps driven by the subpattern:

1. Find the Middle: Use the Fast and Slow pointer technique to locate the center of the list.
2. Reverse the Second Half: This is the application of the In-place Reversal pattern. By reversing the direction of the next pointers in the second half, we convert the structure so that traversing from the "end" (now the new head of the reversed part) moves us towards the middle.
3. Compare: Run two pointers—one from the original head and one from the new head of the reversed section—checking for equality.

Visual Description: Imagine the list 1 -> 2 -> 3 -> 2 -> 1. The middle is 3. We split the list logically. The first half is 1 -> 2 -> 3. The second half is 2 -> 1. We reverse the second half in-place. The list structure effectively becomes: 1 -> 2 -> 3 (First half) 1 -> 2 (Reversed second half, where 1 points to 2 and 2 points to null or 3). We then iterate through both chains simultaneously. 1 matches 1, 2 matches 2.

Algorithm Strategy: Linked List - In-place Reversal

1. Middle Finding: Initialize two pointers, slow and fast, at the head. Move fast two steps and slow one step until fast reaches the end. The slow pointer will effectively mark the start of the second half of the list.
2. In-place Reversal: Treat the node at slow as the head of a sub-list. Use the standard iterative reversal logic (maintaining prev, curr, and next pointers) to reverse all nodes from slow to the end of the list. This transforms the list structure without allocating new nodes.
3. Comparison: Initialize a pointer first at the original head and second at the new head of the reversed half (the last node of the original list). Iterate through both. If values differ, return false.
4. Termination: If the traversal completes without mismatches, return true.
5. Restoration (Optional but Recommended): In a production environment, it is good practice to reverse the second half back to its original state before returning, so the input data remains unmodified.

Execution Flow

1. Initialize Pointers: Set slow = head and fast = head.
2. Locate Middle:
   • Loop while fast and fast.next are not null.
   • Update fast = fast.next.next.
   • Update slow = slow.next.
   • Result: slow is now at the middle (for odd lengths) or the start of the second half (for even lengths).
3. Reverse Second Half:
   • Initialize prev = null and curr = slow.
   • Loop while curr is not null:
     • Save next_temp = curr.next.
     • Point curr.next to prev.
     • Move prev to curr.
     • Move curr to next_temp.
   • Result: prev is now the head of the reversed second half.
4. Check Palindrome:
   • Initialize left = head and right = prev.
   • Loop while right is not null:
     • If left.val != right.val, return false.
     • Advance left = left.next.
     • Advance right = right.next.
5. Return Result: If the loop finishes, return true.

Proof of Correctness

The algorithm relies on the property that a palindrome is symmetric around its center. By reversing the second half, we map the $i$-th node from the end to the $i$-th node from the start of the reversed segment. Comparing the standard forward list with this reversed segment effectively compares $A[i]$ with $A[N-1-i]$. Since the reversal is performed in-place using existing nodes, the space complexity remains constant. The pointers cover every node required for comparison, ensuring no mismatches are skipped.

Reference Implementation

C++ Solution for LeetCode 234

cpp
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;

        // Step 1: Find the middle using Fast and Slow pointers
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: Reverse the second half in-place
        ListNode* prev = nullptr;
        ListNode* curr = slow;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: Compare the first half and the reversed second half
        ListNode* firstHalf = head;
        ListNode* secondHalf = prev; // prev is the new head of the reversed half
        
        while (secondHalf) {
            if (firstHalf->val != secondHalf->val) {
                return false;
            }
            firstHalf = firstHalf->next;
            secondHalf = secondHalf->next;
        }

        return true;
    }
};

Java Solution for LeetCode 234

java
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // Step 1: Find the middle
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse the second half
        ListNode prev = null;
        ListNode curr = slow;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: Compare
        ListNode p1 = head;
        ListNode p2 = prev;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }
}

Python Solution for LeetCode 234

python
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True
            
        # Step 1: Find the middle
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        # Step 2: Reverse the second half
        prev = None
        curr = slow
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            
        # Step 3: Compare
        left = head
        right = prev  # prev is the head of the reversed part
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
            
        return True