Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome (reads the same forward and backward), or false otherwise. Try to solve it in O(n) time and O(1) space.

Example 1

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

Example 2

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

Example 3

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

Solution Approach - Find Middle, Reverse Second Half, Compare

The O(1) space approach uses three steps: find the middle of the list, reverse the second half in-place, then compare the two halves node by node.

Step 1 - Find the middle: Use slow and fast pointers. When fast reaches the end, slow is at the middle.
Step 2 - Reverse second half: Reverse the sublist starting from slow.next.
Step 3 - Compare: Compare nodes from the head and from the reversed second-half head simultaneously. If all values match, it is a palindrome.
Optionally restore the list by reversing the second half again.

Java

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

public class PalindromeLinkedList {

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

        // Step 1: Find middle using slow/fast pointers
        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 secondHalf = reverse(slow);

        // Step 3: Compare first and second halves
        ListNode p1 = head;
        ListNode p2 = secondHalf;
        boolean palindrome = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                palindrome = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // Restore list (optional but good practice)
        reverse(secondHalf);

        return palindrome;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Complexity Analysis:

Time complexity: O(n), finding the middle is O(n/2), reversing is O(n/2), comparing is O(n/2).
Space complexity: O(1) since we reverse in-place and use only a constant number of pointers.