# 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;
}
``````

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only \$19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s \$29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

### More by Jim

Tagged #ctci, #programming, #c, #haskell. All content copyright James Fisher 2020. This post is not associated with my employer.