Problem Description

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

An optimal solution achieves O(n) time complexity and O(1) space complexity by combining a fast-slow pointer approach to find the middle node with a reversal of the latter half of the list.

Algorithm Overview

1. Use two pointers (fast and slow) to locate the middle node of the linked list.
2. Reverse the second half of the list starting from that middle node.
3. Simultaneously traverse the first half (from the head) and the reversed second half, comparing node values.

Code Implementation

struct ListNode {
    int value;
    ListNode* nextNode;
    ListNode() : value(0), nextNode(nullptr) {}
    ListNode(int x) : value(x), nextNode(nullptr) {}
    ListNode(int x, ListNode* next) : value(x), nextNode(next) {}
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->nextNode == nullptr) {
            return true;
        }

        // Step 1: Find the middle node
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->nextNode != nullptr) {
            slow = slow->nextNode;
            fast = fast->nextNode->nextNode;
        }

        // Step 2: Reverse the second half
        ListNode* previous = nullptr;
        ListNode* current = slow;
        while (current != nullptr) {
            ListNode* temporary = current->nextNode;
            current->nextNode = previous;
            previous = current;
            current = temporary;
        }

        // Step 3: Compare first half and reversed second half
        ListNode* left = head;
        ListNode* right = previous;
        while (right != nullptr) {
            if (left->value != right->value) {
                return false;
            }
            left = left->nextNode;
            right = right->nextNode;
        }
        return true;
    }
};

Explanation

Finding the Middle: The fast pointer moves two steps for every one step the slow pointer takes. When the fast pointer reaches the end, the slow pointer is at the middle (or the beginning of the second half for even-length lists).

Reversing the Second Half: Starting from the node pointed to by slow, the links are reversed using a standard in-place reversal algorithm. The variable previous ends up pointing to the new head of the reversed second half.

Comparison: Two pointers start from the original head (left) and the head of the reversed second half (right). They are advanced together, and if any pair of values differ, the function returns false. If all comparisons match, the list is a palindrome.

Example

For the list 1 -> 2 -> 2 -> 1:

1. The slow pointer stops at the second node with value 2.
2. The second half (2 -> 1) is reversed to become 1 -> 2.
3. Comparison: first half (1 -> 2) vs reversed second half (1 -> 2). All values match.
4. Result: true.