Check whether a linked list is a palindrome.
#include <stdbool.h>
static node_t *reverse(node_t *h)
{
node_t *prev = NULL;
while (h) { node_t *n = h->next; h->next = prev; prev = h; h = n; }
return prev;
}
bool is_palindrome_list(node_t *head)
{
node_t *slow = head, *fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
node_t *second = reverse(slow), *p = head, *q = second;
bool ok = true;
while (q) { if (p->val != q->val) { ok = false; break; } p = p->next; q = q->next; }
reverse(second); /* restore the list */
return ok;
}
Points: find the middle with slow/fast pointers, reverse the second half, compare, and restore it (good manners: do not leave the caller's list modified). O(n) time, O(1) space.