## 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.

Pages: 1 2

### 4 Responses to “Palindrome List”

1. r. clayton said

A couple of solutions in Racket.

2. Daniel said

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.out 1 2 3 4 3 2 1
1
\$ ./a.out 1 2 3 4 3 2 1 0
0
```
3. Xero said

``` ```

``` (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))))) ```