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.

Advertisements

Pages: 1 2

2 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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: