Problem Statement

Given the head of a singly linked list, determine whether the sequence of values reads identically forward and backward.

Example 1:

Input: 1 -> 2
Output: false

Example 2:

Input: 1 -> 2 -> 2 -> 1
Output: true

Approach 1: Fast and Slow Pointers with In-Place Reversal

This method achieves O(n) time and O(1) space by temporarily restructuring the list.

Algorithm Steps:

1. Traverse the list using two pointers moving at different speeds to locate the midpoint
2. Reverse the latter half of the list in place
3. Compare node values between the first half and the reversed second half
4. Restore the original list structure for data integrity

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        ListNode midPoint = locateMiddle(head);
        ListNode secondHalfStart = reverseSegment(midPoint.next);
        
        ListNode pointerA = head;
        ListNode pointerB = secondHalfStart;
        boolean isPalin = true;
        
        while (isPalin && pointerB != null) {
            if (pointerA.val != pointerB.val) {
                isPalin = false;
            }
            pointerA = pointerA.next;
            pointerB = pointerB.next;
        }
        
        midPoint.next = reverseSegment(secondHalfStart);
        
        return isPalin;
    }
    
    private ListNode locateMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    private ListNode reverseSegment(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = previous;
            previous = current;
            current = nextTemp;
        }
        
        return previous;
    }
}

Complexity Analysis:

• Time Complexity: O(n) — The list is traversed a constant number of times.
• Space Complexity: O(1) — Only a fixed number of pointer variables are utilized.

Approach 2: Array Conversion with Bidirectional Traversal

A simpler solution that uses additional memory for clarity:

1. Extract all node values into a dynamic array
2. Check for palindrome property using two pointers from opposite ends

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> valueList = new ArrayList<>();
        
        ListNode traversalNode = head;
        while (traversalNode != null) {
            valueList.add(traversalNode.val);
            traversalNode = traversalNode.next;
        }
        
        int left = 0;
        int right = valueList.size() - 1;
        
        while (left < right) {
            if (!valueList.get(left).equals(valueList.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}

Complexity Analysis:

• Time Complexity: O(n) — One full traversal to copy values, followed by O(n/2) comparisons.
• Space Complexity: O(n) — An array is allocated to store all element values.