Palindrome List

October 2, 2018

The simple solution would be to scan through the list and its reversal, but that requires O(n) space to store the reversal and thus fails the requirements.

Our solution is to advance to the middle of the list using Floyd’s tortoise-and-hare algorithm (the hare runs twice as fast as the tortoise, so when the hare is at the end of the list, the tortoise is at the middle), then reverse the second half of the list in-place, compare the two halves, then restore the second half of the list by reversing it a second time. The only extra space is for the pointers to the two halves of the list; the pointers of the list elements are modified in-place to perform the reversal:

(define (reverse! xs)
  (let loop ((prev (list)) (curr xs))
    (if (null? curr) prev
      (let ((next (cdr curr)))
        (set-cdr! curr prev)
        (loop curr next)))))

(define (split xs)
  (let loop ((tortoise xs) (hare xs))
    (cond ((and (pair? hare) (pair? (cdr hare)))
            (loop (cdr tortoise) (cddr hare)))
          ((pair? hare) (cdr tortoise))
          (else tortoise))))

(define (last-pair xs)
  (if (null? (cdr xs)) xs (last-pair (cdr xs))))

(define (palindrome? xs)
  (let ((last (last-pair xs)) (middle (split xs)))
    (let loop ((front xs) (back (reverse! middle)))
      (cond ((null? back) (set! middle (reverse! last)) #t)
            ((= (car front) (car back))
              (loop (cdr front) (cdr back)))
            (else (set! middle (reverse! last)) #f)))))

We wrote the program in pieces so it is clear what each piece does; a more clever implementation could save a pass over the list by combining last-pair and split in a single function. Here are some tests, showing that the function correctly determines if the input is a palindrome and also that the input is properly restored to its original condition:

> (define xs '(1 2 3 4 4 3 2 1))
> (palindrome? xs)
#t
> xs
(1 2 3 4 4 3 2 1)
> (define xs '(1 2 3 4 5 4 3 2 1))
> (palindrome? xs)
#t
> xs
(1 2 3 4 5 4 3 2 1)
> (define xs '(1 2 3 4 5 6 7 8))
> (palindrome? xs)
#f
> xs
(1 2 3 4 5 6 7 8)

You can run the program at https://ideone.com/mGF3sA.

Advertisements

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

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: