Re: Palindrome in Linked list

From: CBFalconer (cbfalconer_at_yahoo.com)
Date: 01/24/05 

Date: Mon, 24 Jan 2005 15:52:34 GMT

amujoo@yahoo.com wrote:
>
> TEchnical Interview question: given that each character of word
> is stored in each node of singly linked list. how would you
> determine that the word is a palindrome?

This should do it:

/* Subject: Palindrome in Linked list Date: 23 Jan 2005 23:41:57
-0800 From: amujoo@yahoo.com Organization:
http://groups.google.com Newsgroups: comp.programming

TEchnical Interview question: given that each character of word
is stored in each node of singly linked list. how would you
determine that the word is a palindrome? */

#include <stdio.h>

#include <stdlib.h>

typedef struct litem { struct litem *next; char ch; } litem,
*litemp; /* ------------------ */ static litem
*appendtolist(litem *oldlist, const char *str) { litem *new;

while (*str) { if (!(new = malloc(sizeof *new))) break; else {
new->next = oldlist; new->ch = *str++; oldlist = new; } } return
oldlist; /* fail by not appending */ } /* appendtolist */ /*
------------------ */ /* believed necessary and sufficient for
NULL terminations */ /* Reverse a singly linked list. Reentrant
(pure) code */ static litem *revlist(litem *root) { litem *curr,
*nxt;

if (root) { /* non-empty list */ curr = root->next; root->next =
NULL; /* terminate new list */ while (curr) { nxt = curr->next;
/* save for walk */ curr->next = root; /* relink */ root = curr;
/* save for next relink */ curr = nxt; /* walk onward */ } } /*
else empty list is its own reverse; */ return root; } /* revlist
*/ /* ------------------ */ static void showlist(litem *list) {
while (list) { putchar(list->ch); list = list->next; } } /*
showlist */ /* ------------------ */ static int qpalind(litem
*list) { char ch;

if (NULL == list) return 1; else { ch = list->ch; if (NULL ==
(list = list->next)) return 1; list = revlist(list); if (ch !=
list->ch) return 0; else { list = list->next; return
qpalind(list); } } } /* qpalind */ /* ------------------ */ int
main(int argc, char **argv) { litem *list; int i;

if (argc < 2) fprintf(stderr, "usage: qpalind string"); else { /*
form full list */ list = NULL; list = appendtolist(list,
argv[1]); for (i = 2; i < argc; i++) { list = appendtolist(list,
" "); list = appendtolist(list, argv[i]); } showlist(list); /*
check for palindrome */ if (qpalind(list)) printf(" is"); else
printf(" is not"); printf(" a palindrome\n"); } return 0; } /*
qpalind main */ 

-- 
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson

Relevant Pages

  • Palindrome in Linked list
    ... TEchnical Interview question: given that each character of word is ... the word is a palindrome? ... Anybody with a cleaner method? ...
    (comp.programming)
  • Re: palindrome
    ... digit number and the program states whether it's a palindrome or not. ... calculate the probability that any given 5 digit number COULD ... compare 1st and last character, ...
    (comp.lang.java.programmer)
  • Re: Determine if a character string is palindromic
    ... I write a function named palindrome to determine if a character ... to determine if a character string is palindromic ... Or, alternatively, you need to define "palindrome" more precisely. ...
    (comp.lang.c)
  • Re: Haha - PvE to PvP transfers now possible
    ... Palindrome wrote in ... every character I see is an alt of someone who has 4 or 5 level 70 ... characters on each of several servers. ... alt in Darkshore and she had this lost look. ...
    (alt.games.warcraft)
  • Re: Palindrome in Linked list
    ... > TEchnical Interview question: given that each character of word is ... hint: recursion. ...
    (comp.programming)