CareerCup

I would traverse the list with slow and fast pointers , with slow pointer visiting every node and fast pointer visiting alternative node.The slow pointer data is stored in a stack until the fast pointer(odd case) or its next reaches null(even case).Now compare the slow poniter data with the element popped from stack.If all the comparisons are true until the stack is empty, then it is a palindrome.

TC- Order of N
SC- O(N)

We can also think of an alternative solution without using the extra space.

/**
	 * Time: O(N)
	 * Space: O(1)
	 */
	public static boolean isListPalindrome(List<Integer> list){
		
		if( list == null ){
			throw new IllegalArgumentException("NULL list can't be checked for palindrome");
		}
		
		if( list.isEmpty() ){
			return true;
		}
		
		final int halfSize = list.size()/2;	
		
		Iterator<Integer> headIt = list.iterator();			
		BigInteger sum1 = sumOfNumbers( headIt, halfSize );
		
		Iterator<Integer> middleIt = getMiddlePointer(list);
		BigInteger sum2 = sumOfNumbers( middleIt, halfSize );		
			
		return sum1.equals(sum2);		
	}

I think ur logic ll not work for list like this 1 2 3 1 2 3.according to ur logic it ll return as a palindrome.but it s not a palindrome right?

I think ur logic ll not work for list like this 1 2 3 1 2 3.according to ur logic it ll return as a palindrome.but it s not a palindrome right?

@ Hari. according to above logic 123 123 is not a palindrome. and the logic is correct,

If we can modify the original list itself then I think we can solve it without using extra space.

1. Just reach the middle element of the the given linked list using slow and fast pointers and from the mid point reverse the second half of the original list.
2. Do a traversal one pointer at start and second at the middle element and compare node by node basis
Overall takes O(n).

Please let me know how you find this.

someone posted this logic for the same question posted earlier. Hope this helps. I thought it's a very elegant way to solve this problem.

bool LinkedList::isPalindrome(){
	if (NULL == head)
	{
		cout<<"List is empty, can't check palindrome property"<<endl;
		return true;
	}
	LinkedListNode *endNode = head;
	LinkedListNode *tempHead = head;
	LinkedListNode **firstNode = &tempHead;
	bool retval = checkPalindrome(firstNode,endNode);
	if (retval)
		cout<<"The List is a palindrome"<<endl;
	else
		cout<<"The List is not a palindrome"<<endl;

	return retval;
}

bool LinkedList::checkPalindrome(LinkedListNode **firstNode, LinkedListNode *endNode){

	//base case
	bool retval = true;
	if (NULL == endNode)
		return retval;

	retval &= checkPalindrome (firstNode, endNode->getNext());
	if (!retval){}
	else if ((*firstNode)->getKey() == endNode->getKey())
		retval = true;
	else
		retval = false;

	*firstNode = (*firstNode)->getNext();

	return retval;
}

Sorry for incorrect solution.

/**
	 * Time: O(N)
	 * Space: O(N/2)
	 */
	public static boolean isListPalindrome(List<Integer> list){
		
		if( list == null ){
			throw new IllegalArgumentException("NULL list can't be checked for palindrome");
		}
		
		if( list.isEmpty() ){
			return true;
		}
		
		List<Integer> firstHalf = getFirstHalf(list);
		Collections.reverse(firstHalf);
		
		Iterator<Integer> middleIt = getMiddlePointer(list);
		Iterator<Integer> firstHalfReversedIt = firstHalf.iterator();
		
		while( middleIt.hasNext() && firstHalfReversedIt.hasNext() ){
			int value1 = firstHalfReversedIt.next();
			int value2 = middleIt.next();
			
			if( value1 != value2 ){
				return false;
			}
		}
		
		return !(middleIt.hasNext() || firstHalfReversedIt.hasNext());
	}

This is one of the ways using XOR.

class Node
{
public Node Next = null;
public int data;
public int count=0;
public Node(int d) { data = d; count++; }

public void AddNewNode(int input)
{
Node newnode = new Node(input);

Node n = this;

while (n.Next != null)
{
n = n.Next;
}
n.Next = newnode;

count++;
}
}

public static bool isLinkedListIsPalindrome(Node myLL)
{
int xorvalue=0,TotalNodes=myLL.count,iteratorval=0,midvalue=0;;
bool ispalindrome = false;
while (iteratorval<TotalNodes)
{
xorvalue = xorvalue^myLL.data;
myLL = myLL.Next;
if(iteratorval==(TotalNodes/2))
{
midvalue = myLL.data;
}
iteratorval++;
}

if ((0 == TotalNodes % 2))
{
if(0==xorvalue)
ispalindrome = true;
}
else
{
if (midvalue == xorvalue)
ispalindrome = true;
}
return ispalindrome;
}

1)We can reverse the linked list until the middle element.(We can find the middle element using slow and fast pointers)
2)Then traverse to the ends of linked list checking the validity of palindrome.
3)Reverse the linked list again until the middle element.
time complexity - O(n),space complexity - 0(1)

We can just reverse the linked list and check if it is same as the original one.

Guys, we can do it without reversing the linked list.

int isPalindrome(**root,*head)
{
	if(!head)
		return 1;
	else
	{
		int res=isPalindrome(root,head->next);
		
		if(res==0)
			return 0;
		int r=(*root)->data==head->data;
		*root=(*root)->next;
		return r;
	}
}

bool isPalindrome(node *head)
{
if(head==NULL || head->next==NULL)return true;
  
node *prev=NULL, *curr=head;
while(curr->next)
{
prev=curr;
curr=curr->n;
}

//Now curr points to last node
if(head->data !=curr->data) return false;
  
//Remove the last node from the list
prev->next=NULL;

//Recursively check for next item from front
return isPalindrome(head->next);
}

I think it is easier than you think. We want to start with the first element in the list and the last element in the list. Then we will compare the values and make sure they are the same as we slowly move towards the inside of the list. If the values do not match at any time, then it is not a palindrome. If the starting variable become > our last variable than we can return.


public boolean checkForPal(List list) {
left = 0;
right = list.size()-1;

while(left <= right) {
if(list.get(left) != list.get(right)) {
return false;
}
left++;
right--;
}
return true;
}