CareerCup

Here's my solution - involves modifying the underlying linked list, but I believe it satisfies the complexity requirements:

- Traverse the list once to determine the total character count.
- Reverse the list from the head up to the center node
- Traverse the list outward in either direction from the center, checking whether the characters form a palindrome.

Here's my stab at it in Java - could probably be cleaned up a bit but seems to work.

boolean isPalindrome(LlNode head) {
        // Determine the length of the string
        LlNode tmp = head;
        int count = 0;
        while(tmp != null) {
            count += tmp.value.length();
            tmp = tmp.next;
        }

        boolean evenLength = count%2 == 0;
        int mid = count/2 + (evenLength ? 0 : 1);

        // Reverse the list up too the node containing the middle character
        count = 0;
        LlNode prev = null;
        tmp = head;
        LlNode next = head.next;
        while((count + tmp.value.length()) < mid) {
            count += tmp.value.length();
            tmp.next = prev;
            prev = tmp;
            tmp = next;
            next = next.next;
        }

        // Advance forward and in reverse from the center node checking if we have a palindrome
        int lPosition = mid-count;
        int rPosition = + (evenLength ? 1 : 0) + lPosition;
        LlNode cLeft = tmp;
        LlNode cRight = tmp;

        boolean isPalindrome = true;
        while(isPalindrome && cLeft != null) {
            if(lPosition < 1) {
                cLeft = cLeft == tmp ? prev : cLeft.next;
                if(cLeft != null) {
                    lPosition = cLeft.value.length();
                }
            }
            if(rPosition > cRight.value.length()) {
                cRight = cRight.next;
                rPosition = 1;
            }
            if(cLeft == null || cRight == null) {
                isPalindrome = cLeft == cRight;
            } else {
                isPalindrome = cLeft.value.charAt(lPosition-- -1) == cRight.value.charAt(rPosition++ -1);
            }
        }
        return isPalindrome;
    }

Pseudo-code:
1. Traverse the list to find the total number of characters
2. Traverse the list again to find the mid character
3. Split the link list to two
4. Reverse the first half
5. Compare two list if they are equal. If yes, return true. Otherwise false.
6. Reverse the first half again
7. Combine the two list together.

Complexity: O(N)
Space: O(1)

Here is a similar amazon interview question: follow this
cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-linkedlist.html

Time complexity should be O(N) and Space Complexity O(1)

import java.util.*;

public class LinkedListPalindrome {
static Boolean isLinkedListPalindrome(){
StringBuilder arr = new StringBuilder();
// create a linked list
LinkedList ll = new LinkedList();
// add elements to the linked list
ll.add("a");
ll.add("bcd");
ll.add("ef");
ll.add("g");
ll.add("f");
ll.add("ed");
ll.add("c");
ll.add("ba");
//System.out.println("Original contents of ll: " + ll+ " " +ll.size());

// remove elements from the linked list

for(int i=0; i<ll.size();i++)
arr.append(ll.get(i));

return(arr.equals(arr.reverse()));
}

public static void main(String args[]) {


System.out.println(isLinkedListPalindrome());

// remove first and last elements

}
}

If it is a doubly link list it is trivial. Start one node from the front and the second node from the back. Time O(n) space O(1)

If it is single link list then keep char[] count for each char, if linklist is palindrome then for each char in [] have even count except one char. The time complexity O(n) and space O(n).

My solution works for the case where each list node contains only one character.

The idea is to recurse all the way to the end, and then compare each character from the end to the beginning (by the ways of returning from recursion) with the character pointed by p. This pointer p is advanced by each recursive function call. For this to work, p needed to be a pointer to pointer. So yeah, not very simple.

I didn't code the check to end the algorithm when the middle of the list is reached.

bool pal(Node**p, Node *q) {
	if (!q) return true;

        // recurse to the end
	if (pal(p, q->next) == false) {
		return false;
	}

	if ((*p)->item != q->item) {
		return false;
	}

        // this is where the pointer p is advanced
	*p = (*p)->next;
	return true;
}

bool palindrome(const List &l) {
	Node *p = l.head->next;
	return pal(&p, p);
}

It is clearly mentioned variable string at each node.

My solution passes through each character only once, and the complexity is O(n), where n is the size of the string. The idea is having four pointers and use a doubly linked list. Another trick is that it uses a node index to determine if the node pointers have met in the middle. The character pointers switch nodes if the two string chunks in the respective nodes are not equal in size.

public class LLPalindrome {
    
    public static void main(String[] args) {
        
        Node root = null;
        Node pointer = null;
        
        int index = 0;
        
        Node lastNode = null;
        
        for (String content : args) {
            if (root == null) {
                root = new Node(content);
                pointer = root;
                root.index = index;
            } else {
                pointer.next = new Node(content);
                pointer.next.index = ++index;
                
                lastNode = pointer.next;
                
                pointer.next.prev = pointer;
                
                pointer = pointer.next;
            }
        }//for
        
        System.out.println(isPalindrome(root, lastNode));
    }
    
    public static boolean isPalindrome(Node root, Node lastNode) {
        
        if (root == null)
            return true;

        Node leftNode = root;
        Node rightNode = lastNode;
        if (rightNode == null)
            leftNode = rightNode;
        String textFromLeft;
        String textFromRight;
        
        int textFromLeftCharPtr;
        int textFromRightCharPtr;

        while (leftNode.index <= rightNode.index) {
            
            textFromLeft = leftNode.content;
            if (leftNode.index == rightNode.index)
                textFromRight = "";
            else
                textFromRight = rightNode.content;
            textFromLeftCharPtr = 0;
            textFromRightCharPtr = textFromRight.length() - 1;
            boolean charactersExpensed = false;
            
            while (!charactersExpensed) {
                char charFromLeft, charFromRight;
                
                if (textFromLeftCharPtr >= textFromLeft.length()) {
                    int indexOnNextText = textFromLeftCharPtr - textFromLeft.length();
                    if (indexOnNextText > textFromRightCharPtr)
                        break;
                    else {
                        charFromLeft = textFromRight.charAt(indexOnNextText);
                    }
                }//if 
                else {
                    charFromLeft = textFromLeft.charAt(textFromLeftCharPtr);
                }//else
                
                if (textFromRightCharPtr < 0) {
                    int indexOnPrevText = textFromLeft.length() + textFromRightCharPtr;
                    if (indexOnPrevText < textFromLeftCharPtr)
                        break;
                    else {
                        charFromRight = textFromLeft.charAt(indexOnPrevText);
                    } 
                }//if
                else {
                    charFromRight = textFromRight.charAt(textFromRightCharPtr);
                }//else
                
                
                if (charFromLeft != charFromRight)
                    return false;
                textFromLeftCharPtr++;
                textFromRightCharPtr--;
                charactersExpensed = textFromLeftCharPtr >= textFromRight.length() &&
                                        textFromRightCharPtr < 0;
            }//while
            leftNode = leftNode.next;
            rightNode = rightNode.prev;
        }//while
        
        
        return true;
        
    }//isPalindrome
    
}

class Node {
    protected Node next;
    protected Node prev;
    protected int index;
    protected String content;
    public Node(String content) {
        this.content = content;
    }
}

====LinkedListPalindrome.java=====
package amazon.coding.test;

import java.util.LinkedList;

public class LinkedListPalindrome {
private LinkedList linkedList = new LinkedList();
private String StringA = new String();
private String StringB = new String();

public LinkedListPalindrome() {

}

public void addNode(String node) {
this.linkedList.add(node);
}

public String linkedListString() {

StringBuilder content = new StringBuilder();

for(int i=0; i<this.linkedList.size(); i++) {
content.append(this.linkedList.get(i));
}

//return content.toString().substring(0, content.toString().length()/2);
//return content.toString().substring(content.toString().length()/2+1, content.toString().length());

this.StringA = content.toString().substring(0, (int)Math.floor(content.toString().length()/2.0));
this.StringB = reverseString(content.toString().substring((int)Math.ceil(content.toString().length()/2.0), content.toString().length()));

return "All String : " + content.toString() + "\n" +
"A String : " + this.StringA + "\n" +
"B String : " + this.StringB;
}

private static String reverseString(String s) {
return ( new StringBuffer(s) ).reverse().toString();
}

public boolean isPalindrome() {
if(this.StringA.equals(this.StringB))
return true;
return false;
}
}


====App.java=====
package amazon.coding.test;

public class App {
public static void main( String[] args ) {
LinkedListPalindrome llp = new LinkedListPalindrome();
llp.addNode("a");
llp.addNode("bcd");
llp.addNode("ef");
llp.addNode("hGh");
llp.addNode("f");
llp.addNode("ed");
llp.addNode("c");
llp.addNode("ba");

System.out.println(llp.linkedListString());
System.out.println(llp.isPalindrome());
}
}

I have thiinked about this problem, don't know whether this one is optimized solution or not ... But it will work in case of single link list as well....
I have taken 3 pointer (p,q,r) and trying to find the middle node by incrementing one pointer by 1 and another one by 2.
Let's say q is pointing to middle of the node and r is pointing to end of the node.
Now for P pointer i will call recursive function call untill "p->next not equal to q" i.e untill p will point left adjacent node of q.
Now match the content of P and q (after incrementing q to q-> next) and if all character of p is parsed then it will return from recursive funtion call untill p is come back to 1st node and similarly if q character contents are parsed then q will point to q->next untill q become last node of link list. Following is the C code for above logic :-

#include<stdio.h>

typedef struct mynode
{
	char *d;
	struct mynode *next;
}node;

node *p,*q,*r;
node a,b,c,d,e,f,g;
node a={"a",&b};
node b={"bc",&c};
node c={"def",&d};
node d={"g",&e};
node e={"fe",&f};
node f={"d",&g};
node g={"cba",NULL};
int index=0;


void rec_call(node *p);
int main()
{
	p=q=r=&a;
	while(r->next!=NULL)
	{
		q=q->next;
		r=r->next->next;
	}
    rec_call(p);
    printf("\n TRUE 	\n\n");
}

void rec_call(node *p)
{
	int l1,l2;
	if(p->next!=q)
	{
		rec_call(p->next);
		l2=strlen(q->d);
	}
	else
	{
		q=q->next;
		l2=strlen(q->d);
	}
	l1=strlen(p->d);
		do
		{	
			if(p->d[l1-1]==q->d[index])
				l1--, index++;
			else
			{
				printf(" \n\n  FALSE \n\n");
				exit(0);
			}
			if(index==l2&&q->next!=NULL)
			{
				q=q->next;
				l2=strlen(q->d);
				index=0;
			}
			if(l1-1==-1)
				return;
		}while(p!=&a && q!=NULL);
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{
        char *data;
        struct node * next;
};

void push(struct node* head, char * input)
{
        struct node * new = (struct node*)malloc(sizeof(struct node));
        new->data = (char *)malloc(strlen(input));
        strcpy(new->data, input);
        new->next = NULL;
        struct node * st = head;
        while(st->next != NULL)
        {
                st = st->next;
        }
        st->next = new;

}

int check(struct node ** head, int fp, int lp, int tail)
{
        int pos = 1;
        struct node* str = *head;
        struct node* str2 = *head;
        while(pos != tail && tail > 1)
        {
                str = str->next;
                pos++;
        }

        if(((*head)->data[fp] ==  str->data[lp-1]))
        {
           if(tail > 1)
           {
                for (pos = 1; pos <= tail - 2; pos++)
                        str2= str2->next;
           }

           if( (*head == str2) && (fp == lp-1))
                {
                        printf("returning 1\n");
                        return 1;
                }
           fp++;
           lp--;
                if((*head)->data[fp] != '\0' && lp > 0)
                {
                        return check(head, fp, lp, tail);
                }
                else if((*head)->data[fp] != '\0' && lp == 0)
                {
                        //for (pos = 1; pos <= tail - 1; pos++)
                        //      str2= str2->next;
                        return check(head, fp, strlen(str2->data), tail-1);

                }
                else if((*head)->data[fp] == '\0' && lp > 0)
                {
                        return check(&((*head)->next), 0, lp, tail-1);
                }
                else if((*head)->data[fp] == '\0' && lp == 0)
                {
                        //for (pos = 1; pos <= tail - 1; pos++)
                        //      str2= str2->next;
                        //printf("next iter\n");
                        return  check(&((*head)->next), 0, strlen(str2->data), tail-2);
                }
                else return 0;


        }
        else
        {
                 printf("%c %c\n",(*head)->data[fp],  str->data[lp-1]);
                 printf("returning 0\n");
                 return 0;
        }
}

main()
{
        int res = 0, i = 1;
        char *input = (char *)malloc(sizeof(char));;
        struct node * head = (struct node*)malloc(sizeof(struct node));
        struct node *st = head;
        head->data = (char *)malloc(sizeof(char));
        printf("enter data: ");

        gets(head->data);

        head->next = NULL;
        while(gets(input))
        {
                push(head, input);
                st = st->next;
                i++;
        }

        printf("end\n");

        res = check(&head, 0, strlen(st->data), i);
        printf("%d\n", res);
}

Hello

This is my code.
Traversing the list from head and tail and check each character. No need to traversing more than once and reversing of list from the middle.

class node {

	public:
		node(const char *value)
		{
			this->value = new char(strlen(value));

			strcpy(this->value, value);
			this->next = NULL;
			this->prev = NULL;
		}

		char *value;
		node *next;
		node *prev;
};

class linkedList {

	public:
		linkedList()
		{
			this->head = NULL;
			this->tail = NULL;
		}

		void insert(const char *value)
		{
			node * newelement = new node(value);

			if(head == NULL) {

				head = newelement;
				tail = newelement;

				return;
			}

			tail->next = newelement;
			newelement->prev = tail;
			tail = newelement;
		}

		int checkPalindrome()
		{
			if(head == NULL)
				return 0;

			node *left = head;
			node *right = tail;
			char *leftValue = left->value;
			char *rightValue = right->value;
			int leftIndex = 0;
			int rightIndex = strlen(rightValue)-1;
			int leftLength = strlen(leftValue);

			while((left->prev != right) && ((left->prev == NULL) || (left->prev->prev != right))) {

				printf("Left: %s\n", leftValue);
				printf("Right: %s\n", rightValue);

				if(leftValue[leftIndex] != rightValue[rightIndex])
					return 0;

				leftIndex++;
				rightIndex--;

				if(leftIndex == leftLength) {

					left = left->next;
					leftValue = left->value;
					leftIndex = 0;
					leftLength = strlen(leftValue);
				}

				if(rightIndex == -1) {

					right = right->prev;
					rightValue = right->value;
					rightIndex = strlen(rightValue) - 1;
				}	
			}

			return 1;
		}

	private:
		node *head;
		node *tail;
};

Can't we do one thing,get all characters in array and simply check if palindrome or not?

One more solution though its a bit space consuming. Break all the string nodes to individual character nodes.
a -> bc -> de -> NULL
will be converted to
a -> b -> c -> d -> e -> NULL
This becomes easy question to solve now. Check whether the linked list is palindrome or not as it contains only single character per node now.