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.

I found it helpful to first write an implementation in Haskell:

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 ([1] :: [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) {
  Node* head = *list;
  if (head == NULL) return NULL;
  *list = head->next;
  return head;
}

void push(Node* head, Node** list) {
  head->next = *list;
  *list = head;
}

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

bool is_palindrome(Node* head) {
  Node* fast = head;
  Node* slow = head;
  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;
}

Node* copy_list(Node* head) {
  if (head == NULL) return NULL;
  return mk_node(head->val, copy_list(head->next));
}

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

This page copyright James Fisher 2020. Content is not associated with my employer. Found an error? Edit this page.

Jim Fisher

CV

Speaking

Blogroll

RSS

TigYog

Kickabout