1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
/**
* 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);
}
};
|
