Palindrome List
October 2, 2018
Today’s exercise sounds like a homework problem:
Write a program that determines if a linked list of integers is palindromic — i.e., reads the same in both directions. Your solution must operate in O(1) space.
Your task is to write a program to determine if a list of integers is palindromic, in O(1) space. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
A couple of solutions in Racket.
Here’s a solution in C.
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node* next; } node_t; int length(node_t* list) { int result = 0; while (list != NULL) { ++result; list = list->next; } return result; } void reverse(node_t** list) { node_t* prev = NULL; node_t* node = NULL; node_t* next = *list; while (next != NULL) { prev = node; node = next; next = next->next; node->next = prev; } *list = node; } bool is_palindrome(node_t* list) { int len = length(list); node_t* mid = list; for (int i = 0; i < len / 2; ++i) { mid = mid->next; } reverse(&mid); node_t* node1 = list; node_t* node2 = mid; bool result = true; for (int i = 0; i < len / 2; ++i) { if (node1->value != node2->value) { result = false; break; } node1 = node1->next; node2 = node2->next; } reverse(&mid); return result; } int main(int argc, char* argv[]) { node_t* list = NULL; for (int i = argc - 1; i > 0; --i) { node_t* node = malloc(sizeof(node_t)); node->value = atoi(argv[i]); node->next = list; list = node; } printf("%d\n", is_palindrome(list)); while (list != NULL) { node_t* node = list; list = node->next; free(node); } return EXIT_SUCCESS; }Examples:
A solution in commonlisp:
https://pastebin.com/5XStJYwq
(defun is-palindrome-p (ints) "return T iff ints is a palindrome. Use constant space" (labels ((aux (xs lower higher) (cond ((null xs) nil) ((> lower higher) t) ((not (= (nth lower xs) (nth higher xs))) nil) (t (aux xs (1+ lower) (1- higher)))))) (aux ints 0 (1- (length ints)))))