---

#include <vector>
using namespace std;

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        // Если список пустой или из одного элемента — это точно палиндром
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        // Шаг 1: Записываем все значения из списка в обычный массив (вектор)
        vector<int> values;
        ListNode* current = head;
        while (current != nullptr) {
            values.push_back(current->val);
            current = current->next;
        }

        // Шаг 2: Проверяем массив с двух концов (два указателя)
        int left = 0;
        int right = values.size() - 1;

        while (left < right) {
            // Если значения не совпадают — это не палиндром
            if (values[left] != values[right]) {
                return false;
            }
            left++;   // двигаем левый указатель вправо
            right--;  // двигаем правый указатель влево
        }

        // Если дошли до конца и все совпало — значит палиндром
        return true;
    }
};