blob: 3f42e4ae18ad8a7326f807d75634a4eb1d834603 (
plain)
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
|
/**
* 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)));
}
};
|
