# How to check whether a linked list is a palindrome

Question 2.7 of Cracking the Coding Interview:

Implement a function to check if a linked list is a palindrome.

One way to implement this is by comparing the list to its reverse (actually, this is almost tautological). This solution is linear-time, and linear-space, which is not bad. But there are solutions which are constant-space - here is one of them.

To start, we’ll find the middle node of the linked list. Then from the middle, we’ll work outwards in both directions, comparing the node values pairwise.

To find the middle node of the list, we can use the “runner” trick: have a `slow` pointer and a `fast` pointer, where the `fast` pointer advances two nodes for every one node that the `slow` pointer advances. When `fast` reaches the end, `slow` is in the middle.

From the middle node, we need to be able to march back up to the start of the list, to compare each value. So we need to also reverse the first half of the list. We do this while we advance the `slow` pointer.

We need to know whether the list has an odd number of nodes (with a middle node), or an even number of nodes (and thus no middle node). We can determine this by how many nodes are left when we hit the end with the fast pointer. If there are an odd number of nodes, we just skip the middle node in the list comparison that follows.

Finally, we should fix up the links in the list that we’ve mutated, and leave it as we found it.

``````module Palindrome where

palindrome :: Eq a => [a] -> Bool
palindrome xs = go xs xs [] where
go (slow:slows) (fast1:fast2:fasts) rev = go slows fasts (slow:rev)
go (slow:slows)  [_]                rev = slows == rev
go slows         fasts              rev = slows == rev

main = print \$
palindrome ([] :: [Int]) &&
palindrome ( :: [Int]) &&
palindrome ([1,1] :: [Int]) &&
not (palindrome ([1,2] :: [Int])) &&
palindrome ([1,2,1] :: [Int]) &&
not (palindrome ([1,2,2] :: [Int])) &&
palindrome ([1,2,2,1] :: [Int]) &&
not (palindrome ([1,2,3,2] :: [Int])) &&
palindrome ([1,2,3,2,1] :: [Int]) &&
not (palindrome ([1,2,3,2,2] :: [Int]))

``````

I then wrote an implementation in C, which follows the same algorithm:

``````#include <stdlib.h>
#include <stdbool.h>
#include <stdarg.h>
#include <assert.h>

typedef struct Node {
int val;
struct Node * next;
} Node;

Node* pop(Node** list) {
if (head == NULL) return NULL;
}

void push(Node* head, Node** list) {
}

void reverse_onto(Node** from_list, Node** to_list) {
Node* node;
while ((node = pop(from_list))) push(node, to_list);
}

bool lists_eq(Node* a, Node* b) {
while (a != NULL) {
if (b == NULL) return false;
if (a->val != b->val) return false;
a = a->next;
b = b->next;
}
return b == NULL;
}

Node* reversed = NULL;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
push(pop(&slow), &reversed);
}
bool ret = lists_eq(
fast == NULL ? slow : slow->next,
reversed);
reverse_onto(&reversed, &slow); // reset list pointers
return ret;
}

// ----------------------------------------------------
// --------------------- TESTS ------------------------

Node* mk_node(int val, Node* next) {
Node* node = malloc(sizeof(Node));
node->val = val;
node->next = next;
return node;
}

Node* mk_list(int len, ...) {
Node* list_start = NULL;
Node* list_end = NULL;
va_list argp;
va_start(argp, len);
for (int i = 0; i < len; i++) {
Node* node = mk_node(va_arg(argp, int), NULL);
if (list_start == NULL) {
list_start = node;
list_end = node;
} else {
list_end->next = node;
list_end = node;
}
}
va_end(argp);
return list_start;
}

if (head == NULL) return NULL;
}

void test_is_palindrome(Node* input, bool expected) {
Node* prev = copy_list(input);
assert(is_palindrome(input) == expected);
assert(lists_eq(input, prev));
}

int main(int argc, char** argv) {
test_is_palindrome(mk_list(0), true);
test_is_palindrome(mk_list(1, 1), true);
test_is_palindrome(mk_list(2, 1,1), true);
test_is_palindrome(mk_list(2, 1,2), false);
test_is_palindrome(mk_list(3, 1,2,1), true);
test_is_palindrome(mk_list(3, 1,2,2), false);
test_is_palindrome(mk_list(4, 1,2,2,1), true);
test_is_palindrome(mk_list(4, 1,2,3,2), false);
test_is_palindrome(mk_list(5, 1,2,3,2,1), true);
test_is_palindrome(mk_list(5, 1,2,3,2,2), false);

return 0;
}
``````
I just released Vidrio, a free app for macOS and Windows to make your screen-sharing awesomely holographic. Vidrio shows your webcam video on your screen, just like a mirror. Then you just share or record your screen with Zoom, QuickTime, or any other app. Vidrio makes your presentations effortlessly engaging, showing your gestures, gazes, and expressions. #1 on Product Hunt. Available for macOS and Windows.

With Vidrio

With generic competitor

### More by Jim

Tagged #ctci, #programming, #c, #haskell. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.