October 2, 2018 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
A couple of solutions in Racket.
By r. clayton on October 4, 2018 at 7:26 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:
By Daniel on October 5, 2018 at 10:11 PM
A solution in commonlisp:
https://pastebin.com/5XStJYwq
By Xero on November 1, 2018 at 11:43 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)))))By Xero on November 5, 2018 at 3:23 PM