146 lines
3.4 KiB
C++
146 lines
3.4 KiB
C++
#include <cassert>
|
|
#include <vector>
|
|
|
|
/**
|
|
* 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) {}
|
|
* };
|
|
*/
|
|
|
|
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) {}
|
|
};
|
|
|
|
namespace {
|
|
|
|
struct middle_t {
|
|
ListNode *node;
|
|
std::size_t size;
|
|
|
|
middle_t(ListNode *node, std::size_t size) : node(node), size(size) {}
|
|
};
|
|
|
|
middle_t find_middle(ListNode *head) {
|
|
ListNode *slow = head;
|
|
ListNode *fast = head->next;
|
|
|
|
std::size_t size;
|
|
for (size = 0; fast != nullptr && fast->next != nullptr; size++) {
|
|
slow = slow->next;
|
|
fast = fast->next->next;
|
|
}
|
|
|
|
return {slow, size};
|
|
}
|
|
|
|
ListNode *reverse_list(ListNode *tail) {
|
|
ListNode *previous = nullptr;
|
|
ListNode *next = nullptr;
|
|
|
|
for (ListNode *current = tail; current != nullptr;
|
|
previous = current, current = next) {
|
|
next = current->next;
|
|
current->next = previous;
|
|
}
|
|
|
|
return previous;
|
|
}
|
|
|
|
bool compare_lists(ListNode *left, ListNode *right, std::size_t size) {
|
|
for (auto i = 0u; i < size + 1; i++) {
|
|
if (left->val != right->val) {
|
|
return false;
|
|
}
|
|
left = left->next;
|
|
right = right->next;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
} // namespace
|
|
|
|
class Solution {
|
|
public:
|
|
bool isPalindrome(ListNode *head) {
|
|
// find middle of the linked list
|
|
auto mid = find_middle(head);
|
|
|
|
// reverse the tail of the linked list
|
|
auto tail = reverse_list(mid.node);
|
|
|
|
// compare head and tail
|
|
return compare_lists(head, tail, mid.size);
|
|
}
|
|
};
|
|
|
|
#pragma region Testing utilities
|
|
namespace {
|
|
|
|
ListNode *construct_list(const std::vector<int> &values) {
|
|
ListNode *head = new ListNode(values.front());
|
|
ListNode *tail = head;
|
|
|
|
for (std::size_t i = 1; i < values.size(); i++) {
|
|
tail->next = new ListNode(values[i]);
|
|
tail = tail->next;
|
|
}
|
|
|
|
return head;
|
|
}
|
|
|
|
void destroy_list(ListNode *linked_list) {
|
|
if (linked_list == nullptr) {
|
|
return;
|
|
}
|
|
destroy_list(linked_list->next);
|
|
delete linked_list;
|
|
}
|
|
|
|
bool test_find_middle(const std::vector<int> &values, int mid_value) {
|
|
auto linked_list = construct_list(values);
|
|
|
|
auto mid = find_middle(linked_list);
|
|
auto result = mid.node->val == mid_value;
|
|
|
|
destroy_list(linked_list);
|
|
return result;
|
|
}
|
|
|
|
bool test_isPalindrome(const std::vector<int> &values) {
|
|
auto linked_list = construct_list(values);
|
|
|
|
Solution s;
|
|
auto result = s.isPalindrome(linked_list);
|
|
|
|
destroy_list(linked_list);
|
|
return result;
|
|
}
|
|
|
|
} // namespace
|
|
#pragma endregion // Testing utilities
|
|
|
|
int main() {
|
|
// find_middle tests
|
|
assert(test_find_middle(std::vector{1, 2, 2, 1}, 2));
|
|
assert(test_find_middle(std::vector{1, 2, 3, 2, 1}, 3));
|
|
assert(test_find_middle(std::vector{1, 2}, 1));
|
|
assert(test_find_middle(std::vector{1}, 1));
|
|
|
|
// isPalindrome tests
|
|
assert(test_isPalindrome(std::vector{1, 2, 2, 1}));
|
|
assert(test_isPalindrome(std::vector{1, 2, 3, 2, 1}));
|
|
assert(!test_isPalindrome(std::vector{1, 2}));
|
|
assert(test_isPalindrome(std::vector{1}));
|
|
|
|
return 0;
|
|
}
|