/**
 * 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:
    // Copy the list.
    ListNode* clone(const ListNode* node) {
        if (!node) return nullptr;
        ListNode* copy = new ListNode();
        copy->val = node->val;
        if (node->next) {
            copy->next = clone(node->next);
        } else {
            copy->next = nullptr;
        }
        return copy;
    }

    // Reverse a list and return the new of the reversed list.
    ListNode* reverse(ListNode* node) {
        if (!node)       return nullptr;
        if (!node->next) return node;
        ListNode* head = reverse(node->next);
        node->next->next = node;
        node->next = nullptr;
        return head;
    }

    // Compare two lists for equality.
    bool eq(const ListNode* a, const LideNode* 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) {
        return eq(head, reverse(clone(head)));
    }
};