## Amazon Interview Question

Software Engineer / Developers Software Engineer in Tests**Country:**India

**Interview Type:**In-Person

```
pseudocode:
1. link list -> a, b, cde, d, c, b, a
g_pointer = head; /*head is pointing to the start of the link list *
2. int recurse(list){
if(list->next) {
recurse(list)
}
/*here you will get the last node containing 'a' */
while(size(last_node)) {
if(g_pointer->data[i] == last_node->data[j]) {
/*so first character matches so move to second one*/
/* but before that we need to make sure that g_pointer has any
more data or not*/
if(strlen(g_pointer->data) == j) /* move to next pointer */ {
g_pointer = g_pointer->next;
j=0;
} else {
i++;j++;
}
} else
return 0; /* means there is no palindrome */
}
}
```

additionally you can check if the total_size_of_palindrome_given_in_the_problem/2 is reached or not.

Object Oriented:

```
def isPalindrome(linkedList):
pl = PalindromeHelper(linkedList)
return pl.isPalindrome(linkedList)
class PalindromeHelper:
def __init__(self, linkedList):
self.leftNode = linkedList;
self.leftIndex = 0
def isPalindrome(self, rightNode):
isPal = True
if rightNode.next != None:
isPal = self.isPalindrome(rightNode.next)
if not isPal: return isPal
rightIndex = len(rightNode.info) - 1
while rightIndex >= 0:
if rightNode.info[rightIndex] != self.leftNode.info[self.leftIndex]:
return False
self.leftIndex = self.leftIndex + 1
rightIndex = rightIndex - 1
if self.leftIndex == len(self.leftNode.info):
self.leftNode = self.leftNode.next
self.leftIndex = 0
return True
```

If you have a doubly linked list, then you can do this in linear time and constant space.

With a singly linked list, you can't do this in constant space unless you're willing to pay for O(N-squared) time. To do it in linear space, you can push the node pointers corresponding to the first N/2 characters on to a stack, then pop them off as you're working through the last N/2 characters. If you don't want to maintain your own stack, you can use recursion, but there's still a stack, so it's still gonna be linear time. And, really, if you're stuck with linear time, then it might be more simple overall to just slurp all your characters into one big string, and then solve the simpler problem of finding out whether a string is palindromic.

Well,

With O(1) space and O(N) time complexity.

This means that while we traverse the list, we need to keep track of already visited characters in come convenient way, without using any extra space.

That thing strikes me with hash comparing hash values of both strings.

Let's compute the length of the original string which in this case comes out to be : 13

so place a pointer on mid of the string, i.e on 'g'.

Now compute hash value of string from 'a' till one element less than 'g' == h1

and compute hash value of the other string from 'g'+1 to end of list == h2

if h1 == h2. then palindrome.

hashing mechanism that could be used (position based) : h = 31*h+ascii(char(i));

your solution looks pretty good.....but here even if you get till the middle node of linked list it may not be the middle of the string.....like it wont be the end of pallindrom string from back side.....please correct me if i m wrong

The hashing mechanism you have suggested doesn't take any positional parameters. If position is not considered your solution is wrong. Also, the second half of the string will be in the reverse order. I am not sure how can you do this algorithm in O(1) space.

@Anjana, We can introduce another parameter like while calculating hash-function by Abhishek.

New function hash-count look like:

h = 31*h*count+ascii(char(i));

for calculating h1 -> increment count from 1 to half of the list i.e. 6 in this case.

And for calculating h2-> decrease count from 6 to 1. This way hash function will start considering order of the character in the string.

Take nod->data from all the nodes and concatenate in string1, then take two pointer, one

moving forward another backward ,move both pointers one by one from both sides check to see if characters are equal till pointers cross esch other, return true if all charaters match else false...........

you cannot use any string or any other data structure to store the contents. Need to do this in o(1) space complexity and o(N) time complexity

this is my code to check palindrome

this is just modified version of checking link list palindrom which contain only one character per node

```
left=head ot LL
right=head of LL
int checkpalindrom(struct nodes **left,struct nodes *right){
static int a=1,b=0,ri=0;
int li,r;
if(right==NULL)
return 1;
b=b+1;
r=checkpalindrom(left,right->next);
if(r==0)
return 0;
li=strlen(right->c);
if(b-a<0)
return 1;
while(li>0){
if(((*left)->c)[ri]!=(right->c)[li-1])
return 0;
li--;
ri++;
if(((*left)->c)[ri]=='\0'){
(*left)=(*left)->next;
a=a+1;
b=b-1;
ri=0;
}
}
return 1;
}
```

its not going backward

first right pointer reached at end

till now left still pointing to head

after this compare

right->data to left->data

if not same return not a link list not palindrom return 0

if same increment (*left)=(*left)->next

return 1

after return 1 left pointing to 2nd node and right pointing to 2nd from last

and so on till b-a>=0

'b' increment from 1

and ' a' decrement from n(number of nodes in list)

when b-a=0 both left and right pointing to middle node

after this we do not need to do nothing simply return 1

this is the idea

try to run following code u will get your answer

```
struct nodes {
char *c;
struct nodes *next;
};
struct nodes *newnodes(char *c){
struct nodes *temp=malloc(sizeof(struct nodes));
temp->c=malloc(sizeof(*c));
strcpy(temp->c,c);
temp->next=NULL;
return temp;
}
void pushs(struct nodes **head,char *c){
struct nodes *temp=*head;
if(*head==NULL){
*head=newnodes(c);
return;
}
*head=newnodes(c);
(*head)->next=temp;
return;
}
void prints(struct nodes *head){
struct nodes *t=head;
while(t!=NULL){
printf("%s-->",t->c);
t=t->next;
}
printf("NULL \n");
}
int checkpalindrom(struct nodes **left,struct nodes *right){
static int a=1,b=0,ri=0;
int li,r;
if(right==NULL)
return 1;
b=b+1;
r=checkpalindrom(left,right->next);
if(r==0)
return 0;
li=strlen(right->c);
if(b-a<0)
return 1;
while(li>0){
if(((*left)->c)[ri]!=(right->c)[li-1])
return 0;
li--;
ri++;
if(((*left)->c)[ri]=='\0'){
(*left)=(*left)->next;
a=a+1;
b=b-1;
ri=0;
}
}
return 1;
}
void main(){
struct nodes *head=NULL;
struct nodes *left;
struct nodes *right;
//a-->bcd-->ef-->g-->f-->ed-->c-->ba.
//a-->bcd-->efgf-->edc-->ba
pushs(&head,"ba");
pushs(&head,"edc");
pushs(&head,"efgf");
pushs(&head,"bcd");
pushs(&head,"a");
//pushs(&head,"zgy");
//pushs(&head,"ef");
//pushs(&head,"bcd");
//pushs(&head,"a");
left=head;
right=head;
prints(head);
printf("\n%d\n",checkpalindrom(&left,right));
prints(head);
}
```

with out recursion we have to reverse half list

following isolution is with out recursion

```
struct nodes *reverse(struct nodes *head){
struct nodes *p=NULL;
struct nodes *c=head;
struct nodes *n=head->next;
while(c!=NULL){
c->next=p;
p=c;
c=n;
if(n!=NULL)
n=n->next;
}
return p;
}
int checkpalindrom2(struct nodes *head){
char *r;
struct nodes *t=head;
struct nodes *s=head;
struct nodes *f=head;
int ri,li,a,b;
while(f->next!=NULL && f->next->next!=NULL){
s=s->next;
f=f->next->next;
}
s->next=reverse(s->next);
f=s->next;
li=0;
while(f!=NULL){
ri=strlen(f->c);
while(ri>0){
if((t->c)[li]!=(f->c)[ri-1]){
s->next=reverse(s->next);
return 0;
}
ri--;
li++;
if((t->c)[li]=='\0'){
t=t->next;
li=0;
}
}
f=f->next;
}
if((t->c)[li]!='\0'){
r=malloc(strlen(&(t->c)[li]));
strcpy(r,&(t->c)[li]);
li=0;
ri=strlen(r);
while(ri>li){
if(r[li]!=r[ri-1]){
s->next=reverse(s->next);
return 0;
}
li++;
ri--;
}
}
s->next=reverse(s->next);
return 1;
}
```

first reached at mid point

then reverse last half

then start comparing from head to last half reversed list

then again reverse last half to retain orignal list

try to run this code u will understand

now space complexity is O(1)

please comment if something seems wrong

You cant reach the midpoint without knowing the size of linked list. :(

Probably, a dequeue might help where we fill it up first, and compare it from both the sides by popping one character from both ends.

we can reach mid point of linklist without knowing its size

just take two pointer fast and slow

initialy

```
struct node *mid(struct node *head){
struct node *fast=head
struct node *slow=head
while(fast->next!=NULL && fast->next->next!=NULL){
slow=slow->next;
fast=fast->next->next
}
return slow;
}
fast->next!=NULL condition for LL of odd number of node
fast->nex->nextt!=NULL condition for LL of even number of node
after this slow point to mid point of LL
```

Jay try to run above code post by me u will find it is working properly

@Dhamu

Can u please elaborate for this example(5 nodes):

abcdef -> ghihgfed -> c -> b -> a

If any node can hold any amount of data, then we could append seconds node's data into first one ...and third node's also in first node...and so on ...we keep appending each node's data into first node.

Finally first node contains a string , which we have to find is a palindrome or not.

@ sK thanks i was also thinking about this case

my iretrative solution wrongly asume that mid point of combined string lies in mid point of LL ,which can,t give correct answer to your case(abcdef -> ghihgfed -> c -> b -> a)

in your example mid point of combined string lies in second node

which is not mid point of list so its does not give correct answer

but my recursive solution will work for this but it takes O(n) space due to recursion

i m try to modifie my iretrative soln to work for all case

thanks sK once again for this example because of this i find error on my code

i will back with update soln

Take @pm solution and convert it to C#. One thing to improve though, it traverse through the full length of the linkedlist to determine Pallindrome - we only have to go through half that many.

```
using System;
using System.Collections.Generic;
using System.Text;
namespace Pallindrome
{
class Pallindrome
{
static void Main1(string[] args)
{
//string s1 = "civic";
//string s2 = "ciic";
//string s3 = "xx";
//string s4 = "x";
//string s5 = "";
//string s6 = null;
//string s7 = "chu";
//PrintPallindrome(s1);
//PrintPallindrome(s2);
//PrintPallindrome(s3);
//PrintPallindrome(s4);
//PrintPallindrome(s5);
//PrintPallindrome(s6);
//PrintPallindrome(s7);
int i1 = 1234321;
int i2 = 1;
int i3 = 1121;
PrintPallindrome(i1);
PrintPallindrome(i2);
PrintPallindrome(i3);
}
static void PrintPallindrome(int i)
{
if (IsPallindrome(i))
Console.WriteLine("yes");
else
Console.WriteLine("no");
}
static bool IsPallindrome(int n)
{
int div = 1;
int len = 1;
while (n / div > 10)
{
div *= 10;
len++;
}
if (len == 1) return true;
for (int i = 0, j=len-1; i < j; i ++, j--)
{
int l = n / div;
int r = n % 10;
if (l != r) return false;
//n = (n - l * div - r) / 10;
n = n % div / 10;
div /= 100;
}
return true;
}
static void PrintPallindrome(string s)
{
if (IsPallindrome(s))
Console.WriteLine("yes");
else
Console.WriteLine("no");
}
static bool IsPallindrome(string s)
{
if (s == null || s == string.Empty)
return false;
int len = s.Length;
for (int i=0, j=len-1; i<j; i++, j--)
{
if (s[i]!=s[j]) return false;
}
return true;
}
}
class PallindromeLinkedList
{
static LinkedListNode<string> head = null;
static int curIndex = 0;
static int len;
static void Main()
{
string[] words = { "acb", "bc", "defdc", "bbca" };
LinkedList<string> ll = new LinkedList<string>(words);
head = ll.First;
len = head.Value.Length;
if (true == IsPallindrome2(head))
Console.WriteLine("yes");
else
Console.WriteLine("no");
}
static bool IsPallindrome2(LinkedListNode<string> node)
{
int i;
bool isPal = true;
if (node.Next != null)
{
isPal = IsPallindrome2(node.Next);
}
if (isPal)
{
for (i = node.Value.Length - 1; i >= 0; i--)
{
char[] arr = node.Value.ToCharArray();
if (arr[i] == (char)head.Value.ToCharArray().GetValue(curIndex))
{
curIndex++;
if (curIndex >= len)
{
curIndex = 0;
head = head.Next;
if (head!=null) len = head.Value.Length;
}
}
else
return false;
}
return true;
}
return false;
}
}
}
```

first traverse whole list nd calc length of list; after n/2 + 1 element till nth element reverse the list. now u have 2 list , compare both list element one by one

reversing a linked list can be done quite easily . But here other than reversing the lined list , you also need to reverse the characters inside the node . Doing that also wont be an issue . The problem comes when n/2+1 element will be part of the same node :- For example in a-->bcd-->efgf-->edc-->ba.... After calculating length as 13 , we have to reverse from 7th element , how will you achieve this when you have to reverse some part and leave the remaining part and in the end do not hamper the original structure of the linked list

public static boolean isLLPalindrome(LinkedList<String> list){

String s = "";

for(int i=0;i<list.size();i++)

s = s+list.get(i);

return isPalindrome(s);

}

public static boolean isPalindrome(String abc){

int mid = abc.length()/2;int i=-1,j=-1;

if(abc.length()%2==0){

i=mid-1;j=mid;

}else

i=j=mid;

for(; j>=0; i++,j--){

if(abc.charAt(i)==abc.charAt(j))

continue;

else

return false;

}

return true;

}

Traverse LL and get total no of character "n".

Traverse again starting from root and keep pushing the character into stack until ti reaches to size of n/2, escape 1 character if n is odd. and start traversing from this point while each character comes next pop a character from stack and compare it to current character . if it not same return false.

if any one of the stack or LL end return false

otherwise return true(when both stack and LL ends together )

whole we need to traverse 2 times, so O(n)

and need stack of size n/2, so O(n) again.

i don't get what you(REAMS.AL) want to say

O(1) space and O(n) time solution:

1.) traverse the LL to find the size of all letters(we do not care about the size of the LL).

2.) find the middle charecter MID = n >> 1 - 1.

3.) traverse the LL to find in which node MID character is.

4.) split the node int two parts - 1st part with the characters before mid(included), 2nd with chars after MID.

5.) reverse the second part of the LL (including the 2nd splitted node)

6.) traverse with two pointers 1st from the start, 2nd to the reversed part, untill we hit MID

7.) after 6.) we know if this is palindrom just need to restore the LL if the task require it --> will skip the restoring since it will be easy, just undo what you have done till step 5

Using single linked list, while traversing list, each time concatenate the present node key to previous node key. At the end of traversal the last node key contains the whole list characters. then apply your palindrome technique on final node key. traversal will take O(n) complexity and palindrome check will take O(n). So time complexity can be approximate to O(n) and since we didn't use any new keys space complexity remains same i.e O(1). Plese let me know if i am wrong.

step 1 recurse through the list and count the total length of string, in case of this example count is 13

step 2 Math.ceil(count/2) = 7 in case of example data

step3 recurse through the list node with two head pointer increment both pointer and reverse the string from position 8 to last so new list will be like

a - bcd - ef - g - ab - c - de - f

step4 recurse through the list with 2 pointers keep 1st at head and move 2nd to 8th position then using runner technique keep matching 1st char to 8th, 2nd to 9th till 6th to 13th all matched return true.

O(n)

Lets take the example as a-->bcd-->efgf-->edc-->ba.....The above approach needs to be updated on cases where the middle element falls in the middle of a given node.

step3: How to reverse the String? We need to reverse the half list and then reverse the node member char arrays in each node..Then, reversing the half-list is not a O(n) operation..Is there any way to reverse a list in O(n)?

```
package algo.solutions;
import algo.datastructures.LinkedList;
public class PalindromeList {
public static void main(String[] args)
{
LinkedList list = new LinkedList(new char[]{'m', 'a'}, new LinkedList(new char[] {'l','a','y'}, new LinkedList(new char[] {'a', 'l', 'a', 'm'}, null)));
LinkedList[] l = new LinkedList[1];
l[0] = list;
System.out.println(isPalin(list, new int[1], l));
list = new LinkedList(new char[]{'a'}, new LinkedList(new char[] {'b','c','d'}, new LinkedList(new char[]{'e','f'},
new LinkedList(new char[] {'g'}, new LinkedList(new char[] {'f'}, new LinkedList(new char[] {'e','d'}, new LinkedList(new char[] {'c'},
new LinkedList(new char[]{'b','a'}, null))))))));
l[0] = list;
System.out.println(isPalin(list, new int[1], l));
}
private static boolean isPalin(LinkedList tail, int[] headPt, LinkedList[] head)
{
if(tail == null)
{
return true;
}
boolean ret = true;
if(tail.next != null)
{
ret = isPalin(tail.next, headPt, head);
}
if(ret)
{
char[] tailchar = (char[])tail.value;
int tailPt = tailchar.length-1;
while(true )
{
char[] headchar = (char[])head[0].value;
if(headchar[headPt[0]++] != tailchar[tailPt--])
{
return false;
}
if(headPt[0] == headchar.length)
{
head[0] = head[0].next;
headPt[0] = 0;
}
if(tailPt == -1)
{
break;
}
}
}
return ret;
}
}
```

bool isListPalindrome(SNODE *head, SNODE *tail)

{

int i, j;

int hlen, tlen;

SNODE *p, *r;

p = head;

r = tail;

hlen = strlen(p->str);

tlen = strlen(r->str);

i = 0;

j = tlen-1;

while(p != r)

{

while(i<hlen && j>=0)

{

if(p->str[i] == r->str[j])

{

i++;

j--;

}else

{

return FALSE;

}

}

if(i==hlen)

{

p = p->next;

i = 0;

hlen = strlen(p->str);

}

if(j<0)

{

r = r->pre;

tlen = strlen(r->str);

j = tlen-1;

}

}

return TRUE;

}

I have compiled an implementation with some of the ideas already proposed. Basically, I find the middle char of the whole String and then reverse the second part of the list followed by linear char comparisons of the first part and the second reversed parts. I am not sure whether this a true O(n) time complexity since the reversing part takes more and there is no other way to avoid. Space is O(1). I have covered the boundary case where the middle char is positioned either at the beginning of the node char array or in some other position!

private static boolean isPalindrome(ListNode head) {

ListNode curr = head;

int charArrSize = 0;

while (curr != null) {

charArrSize += curr.member.length;

curr = curr.next;

}

int mid = 0;

if (charArrSize % 2 == 0) {

mid = (charArrSize / 2) + 1;

} else {

mid = (charArrSize / 2) + 2;

}

curr = head;

ListNode midNode = null;

ListNode cNode = null;

char midChar = ' ';

int currSize = 0;

int midIdx = 0;

boolean flag = false;

while (curr != null && !flag) {

int size = curr.member.length;

for (int i = 0; i < size; i++) {

currSize++;

if (currSize == mid) {

if (i == 0) {

midNode = curr;

} else {

midNode = curr.next;

}

midChar = curr.member[i];

midIdx = i;

flag = true;

break;

}

}

curr = curr.next;

}

curr = head.next;

cNode = head;

while (curr != midNode) {

curr = curr.next;

cNode = cNode.next;

}

if (midNode == null || midChar == ' ') {

return false;

}

ListNode mNode = reverseMidList(midNode);

cNode.next = mNode;

int i = 0;

int j = 0;

if (midIdx == 0) {

curr = mNode;

i = 0;

} else {

curr = midNode;

i = midIdx;

}

j = curr.member.length - 1;

while (curr != null) {

while (i <= j) {

char temp = curr.member[i];

curr.member[i] = curr.member[j];

curr.member[j] = temp;

i++;

j--;

}

curr = curr.next;

if (curr != null) {

i = 0;

j = curr.member.length - 1;

}

}

char first = head.member[0];

char second = ' ';

ListNode firstNode = head;

ListNode secondNode = null;

if (midIdx == 0) {

secondNode = mNode;

} else {

secondNode = midNode;

}

int firstIdx = 0;

int secondIdx = 0;

int sz = secondNode.member.length;

for (i = 0; i < sz; i++) {

if (secondNode.member[i] == first) {

second = secondNode.member[i];

secondIdx = i;

break;

}

}

if (first != second) {

return false;

}

flag = false;

while (!flag) {

if (secondNode == null) {

flag = true;

continue;

}

if (firstNode.member[firstIdx] != secondNode.member[secondIdx]) {

return false;

}

if (firstIdx < firstNode.member.length - 1) {

firstIdx++;

} else {

firstNode = firstNode.next;

firstIdx = 0;

}

if (secondIdx < secondNode.member.length - 1) {

secondIdx++;

} else {

secondNode = secondNode.next;

secondIdx = 0;

}

}

return true;

}

private static ListNode reverseMidList(ListNode head) {

if (head == null || head.next == null) {

return head;

}

ListNode restReverse = reverseMidList(head.next);

ListNode curr = restReverse;

while (curr.next != null) {

curr = curr.next;

}

curr.next = head;

head.next = null;

return restReverse;

}

I have implemented the problem in O(number of characters stored in the Linked list).

```
private static boolean isPalindrome(SingleLinkedList list)
{
if(list!=null)
{
Node fp=list.getHead();
Node sp=list.getHead();
while(fp!=null&&sp!=null)
{
sp=sp.getNext();
if(sp!=null)
{
sp=sp.getNext();
if(sp!=null)
{
fp=fp.getNext();
}
}
}
//fp contains last node in the first part
//reverse second part
Node temp=fp.getNext();
Node prev=null;
while(temp!=null)
{
Node temp1=temp.getNext();
temp.setNext(prev);
prev=temp;
temp=temp1;
if(temp==null)
{
fp.setNext(prev);
}
}
Node fp1=list.getHead();
Node sp1=fp.getNext();
int fcount=0;
int scount=-1;
while(fp1!=null&&sp1!=null)
{
char[] fa=fp1.getData().toString().toCharArray();
char[] sa=sp1.getData().toString().toCharArray();
if(scount==-1)
{
scount=sa.length-1;
}
while(fcount<fa.length&&scount>=0)
{
if(fa[fcount++]!=sa[scount--])
return false;
}
if(fcount<fa.length)
{
scount=-1;
sp1=sp1.getNext();
}
else if(scount>=0)
{
fcount=0;
fp1=fp1.getNext();
}
else
{
scount=-1;
sp1=sp1.getNext();
fcount=0;
fp1=fp1.getNext();
}
}
}
return true;
}
```

```
Recursive approach: space O(1) ; time O(n) approx
//Class level variables
int totalLength;
int reversePtr;
int forwardPtr;
int innerFwdPtr;
int innerRevPtr;
Node fwdNode;
boolean isPal = true;
private void recurseNode(Node n) {
if (n==null) {
return;
}
//assumption node does not have empty string
totalLength=totalLength+n.value.length();
recurseNode(n.next) ;
if (!isPal) {
return;
}
for(int i=n.value.length()-1;i>=0;i--,innerFwdPtr++,forwardPtr++) {
if(forwardPtr>=totalLength/2) {
break;
}
char ch = n.value.charAt(i);
if (innerFwdPtr>=fwdNode.value.length()) {
fwdNode=fwdNode.next;
innerFwdPtr=0;
}
//check each char at a time last char vs first char so on ..
if (ch==fwdNode.value.charAt(innerFwdPtr)) {
}else {
isPal=false;
return;
}
}
return;
}
```

O(n) Time, space O(1).

Using the idea of hashing of characters (someone mentioned earlier) to check if the string is a palindrome. Can use SHA1 or MD5 or custom hasing logic.

Thought is -

1) Reverse the linked list in forward walk (interatively). In this step, add each character to the hash. So the hashing would be done on the string "abcdefgfedcba"

2) Now that the linklist is reversed, we can reverse this reversed linked list back to the original list. During this step, we will hash the characters from last to first. For e.g.: for the 2nd node in original list "bcd", we should hash characters in the reverse order (ie. "dcb") during this step.

3) f the string is a palindrome, forward walk hash value and backward walk hash value will be same. Return true if so. Else false.

Do a recursive traversal of the list and check if nth char from beginning is equal to nth char from the end. Something like below. I haven't verified it

```
bool is_palind = true;
node *head;
int index=0;
char
get_next() {
if(!head) {
return '\0';
}
if(index == head->data.size()) {
/* Done with this node's data */
head = head->next;
index = 0;
return head->data[index++];
} else {
/* return the next char */
return head->data[index++];
}
}
void
recurse(node *p) {
if(p == NULL) {
return 0;
string front = head->data;
} else {
int back_index = recurse(p->next);
string back_data = p->data;
int n = back_data.size();
for(int i=0; i<back_data.size(); i++) {
/* CHeck if n-th char from last is same as nth char from beginning */
if(x[n-i-1] != get_next()) {
is_palind = false;
}
back_index++;
}
return back_index;
}
}
bool
is_list_palindrome(node *ip) {
head = ip;
recurse(ip);
retutn is_palid;
}
struct node {
public:
string data;
node* next;
};
```

Do a recursive traversal of the list and check if nth char from beginning is equal to nth char from the end. Something like below. I haven't verified it

bool is_palind = true;

node *head;

int index=0;

char

get_next() {

if(!head) {

return '\0';

}

if(index == head->data.size()) {

/* Done with this node's data */

head = head->next;

index = 0;

return head->data[index++];

} else {

/* return the next char */

return head->data[index++];

}

}

void

recurse(node *p) {

if(p == NULL) {

return 0;

string front = head->data;

} else {

int back_index = recurse(p->next);

string back_data = p->data;

int n = back_data.size();

for(int i=0; i<back_data.size(); i++) {

/* CHeck if n-th char from last is same as nth char from beginning */

if(x[n-i-1] != get_next()) {

is_palind = false;

}

back_index++;

}

return back_index;

}

}

bool

is_list_palindrome(node *ip) {

head = ip;

recurse(ip);

retutn is_palid;

}

struct node {

public:

string data;

node* next;

};

Approach:

1. By using Array:

-Find the total no. of char by node traversal in List= length

-Have an Array and put length/2 char from List [first char to length/2 char]

-now start traversing from (length-length/2)th char and compare with Array's last char

-in case match move one more char in node or next node in case previous char was the last char in node and compare Array's second last char..... continue till end

2. The great Recursion:

-initialize a global pointer *ptr with head of list

-go till the end in recursive function which returns an object of Class ReturnValue {Node* node;int index}

[write code in recursive fun after calling recursive method ]

-Once reached to the end process last node(got through recursion loop) and *ptr node

-Compare last (got through recursion loop) node's char set to *ptr node char set

-Go to the last (got through recursion loop) node's last char and match with *ptr node's first char

-in case match found

-check for ptr node's next char to last (got through recursion loop) node's second last char

-in case ptr node had only one char move global ptr to next node [ptr=ptr->next]

-in case last (got through recursion loop) node had only one char then exit from last recursive function and return ptr node and index of char in ptr node keeping in a object of Return Value.

-now last recursive fun will be exited and recursive fun will point to second last node of the list

-perform same operation.

edit: do not skip N/2 nodes, skip nodes until skipped nodes contain half of the characters (which may not necessarily be N/2)

import java.util.LinkedList;

import java.util.List;

/**

*

* @author Ralph

*/

public class Palindrome {

public boolean isPalindrome(List<String> list) {

String forward = "";

String backward = "";

for (int i = 0; i < list.size(); i++) {

forward = forward + list.get(i);

backward = backward + reverse(list.get((list.size() - 1 - i)));

}

if (forward.equalsIgnoreCase(backward)) {

return true;

}

return false;

}

public String reverse(String string) {

String reverse = "";

for (int i = (string.length() - 1); i >=0; i--) {

reverse = reverse + string.charAt(i);

}

return reverse;

}

public static void main(String [] args) {

List<String> list = new LinkedList<String>();

list.add("re");

list.add("vi");

list.add("ver");

Palindrome p = new Palindrome();

System.out.println(p.isPalindrome(list));

}

}

Use Doubly Circular linked list. Traverse with one pointer from front and one from back

- pm March 27, 2013