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

Posted by programmingpraxis
Filed in Exercises
4 Comments »

4 Responses to “Palindrome List”

  1. r. clayton said
    October 4, 2018 at 7:26 PM

    A couple of solutions in Racket.

  2. Daniel said
    October 5, 2018 at 10:11 PM

    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
  4. Xero said
    November 5, 2018 at 3:23 PM 


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

Leave a comment