/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // Return the length of the list.
    size_t length(const ListNode* node) {
        if (!node) return 0;
        return 1 + length(node->next);
    }

    // Return the nth element of the list.
    const ListNode* nth(const ListNode* node, size_t n) {
        if (!node)  return nullptr;
        if (n == 0) return node;
        return nth(node->next, n-1);
    }

    // Reverse the list up to, and not including, the nth element.
    // Return the head of the reversed list (nth-1 node).
    ListNode* reverse(ListNode* node, size_t n) {
        if (!node)       return nullptr;
        if (!node->next) return node;
        if (n == 1) {
            node->next = nullptr;
            return node;
        }

        ListNode* head = reverse(node->next, n-1);
        node->next->next = node;
        node->next = nullptr;
        return head;
    }

    // Compare two lists for equality.
    bool eq(const ListNode* a, const ListNode* b) {
        if (!a && !b)         return true;
        if (!a)               return false;
        if (!b)               return false;
        if (a->val != b->val) return false;
        return eq(a->next, b->next);
    }

    bool isPalindrome(ListNode* head) {
        if (!head)       return true;
        if (!head->next) return true;

        // If odd,  get the middle element.
        // If even, get the first element of the second half.
        const size_t len      = length(head);
        const size_t middle   = len/2;
        const ListNode* head1 = nth(head, middle + (len & 1));
        const ListNode* head2 = reverse(head, middle);
        return eq(head1, head2);
    }
};