</>EmbeddedInterview

Check whether a linked list is a palindrome.

Medium"Coding: Linked Lists, Stacks & Queues"
#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.