### 题目描述

Given a singly linked list, determine if it is a palindrome.

### 例子

#### 例子 1

Input: `1->2` Output: `false`

#### 例子 2

Input: `1->2->2->1` Output: `true`

• Could you do it in O(n) time and O(1) space?

### 解题思路

`````` * 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:

// compute the length of linked list
int n = 0;
while(curr) {
curr = curr->next;
n++;
}
if (n <= 1) return true;

// move curr to the second half of linked list
for (int i = 0; i < n / 2; i++) {
curr = curr->next;
}
if (n % 2) {
curr = curr->next;
}

// reverse the second half of linked list
ListNode *prev = nullptr;
ListNode *next = curr->next;
curr->next = prev;
while(next) {
prev = curr;
curr = next;
next = curr->next;
curr->next = prev;
}

// compare the first half & reversed second half
if (curr->val != head->val) return false;
curr = curr->next;
}

return true;
}
};
``````
• 时间复杂度: O(n)
• 空间复杂度: O(1)