Home » Interview coding problems/challenges

Palindrome Linked List

In this article, we are going to see how to check a single linked list whether it's palindrome or not? This problem can be featured in interview coding rounds. Submitted by Radib Kar, on January 11, 2019

Problem statement

Given a singly linked list, determine if it is a palindrome. Write a Boolean function to output true or false based on result.

Input Example:

    Example 1:
    Input: 1->2->3->NULL
    Output: false

    Example 2:
    Input: 1->2->2->1->NULL
    Output: true

Solution

For a single linked we don't have a prev pointer to traverse back from the end of the list and to check with corresponding start positions, i.e., what we normally do to check a string to be palindrome. But for a single linked list we only can traverse forward.

Algorithm

1.  Declare a global temp variable 
    ListNode* temp;   
//function which pass head pointer to check whether it's palindrome    
2.  bool isPalindrome(ListNode* head) 
        temp=head;
        return checkPalindrome(head);
    End Function

3.  Recursive function :
    boolcheckPalindrome(ListNode* p)
        a.  Check for base case
		    IF p==NULL
		        return true;
        b.  bool result=checkPalindrome(p->next) &(temp->data==p->data);
        c.  Traverse tempby one step.
                temp=temp->next;
    	return result;
    END FUNCTION

Attention here!!!

For any statement like, bool result=checkPalindrome(p->next) &(temp->data==p->data);

Where there is two expression linked with ‘&' or ‘&&' operator the first expression is evaluated first and in case if it's true, only the second expression is evaluated. If the first expression is false, second expression is not at all evaluated.

So for this particular statement,

checkPalindrome(p->next) is kept being evaluated until recursion reaches the base case & (temp->data==p->data) is not at all evaluated until the first expression results true .

Let's evaluate how the function works to check whether it's a palindrome.

For example 2:

The list is 1->2->2->1->NULL
Head=1

The main function calls isPalindrome(head)
It sets temp to head and calls checkPalindrome(head)
For the rest of the evaluation a node is represented by 
its value for better visualization & understanding
checkPalindrome(1)   //record no 0
base case not matched
bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
[]=not evaluated part ,bold and underlined too
Call to checkPalindrome(1->next)->checkPalindrome(2)
----------------------------------------------------------

checkPalindrome(2) //record no 1
base case not matched
bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
[]=not evaluated part ,bold and underlined too
Call to checkPalindrome(2->next)->checkPalindrome(2)
----------------------------------------------------------

checkPalindrome(2) //record no 2
base case not matched
bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
[]=not evaluated part ,bold and underlined too
Call to checkPalindrome(2->next)->checkPalindrome(1)
----------------------------------------------------------

checkPalindrome(1) //record no 3
base case not matched
bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
[]=not evaluated part ,bold and underlined too
Call to checkPalindrome(1->next)->checkPalindrome(NULL)
----------------------------------------------------------

checkPalindrome(NULL) //record no 4
base case matched
it returns true
----------------------------------------------------------


At record no 3:
bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
checkPalindrome(1->next) is true , hence next expression evaluated
Now, temp is the global variable which was initialized head 
in the isPalindrome function, temp hasn't been changed yet
Temp->data=1
P at record 3 is 1 (data part 1)
Thus temp->data==p->data
Hence result=true & true= true
Now temp=temp->next=2
And this record returns true to the 
caller function(checkPalindrome(2->next)) (At record 2) 
----------------------------------------------------------

At record no 2:
bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
checkPalindrome(2->next) is true (returned from record no 3),
hence next expression is evaluated
Temp->data=2
P at record 2 is 2 (data part 2)
Thus temp->data==p->data
Hence result=true & true= true
Now temp=temp->next=2
And this record returns true to the caller 
functioncheckPalindrome(2->next) (At record 1) 
----------------------------------------------------------

At record no 1:
bool result = checkPalindrome(2->next) &[(temp->data==p->data)]
checkPalindrome(2->next) is true (returned from record no 2) , 
hence next expression is evaluated
Temp->data=2
P at record 1 is 2 (data part 2)
Thus temp->data==p->data
Hence result=true & true= true
Now temp=temp->next=1
And this record returns true to the caller 
functioncheckPalindrome(1->next) (At record 0) 
----------------------------------------------------------

At record no 0:
bool result = checkPalindrome(1->next) &[(temp->data==p->data)]
checkPalindrome(1->next) is true , hence next expression evaluated
Temp->data=1
P at record 0 is 1 (data part 1)
Thus temp->data==p->data
Hence result=true & true= true
Now temp=temp->next=NULL
And this record returns true to the 
caller function(isPalindrome(head)) (At main) 

Thus it returns true.
Of course 1->2->2->1->NULL is a valid palindrome.
Similarly you can check for 1->2->3->NULL. Do it yourself!!

Hints:
(It's not a Palindrome)
It will return false at some record & so on.

C++ implementation

#include <bits/stdc++.h>
using namespace std;

class ListNode{ //list node structure
    public:
    int data;
    ListNode* next;
};

ListNode* creatnode(int d){ //create node for single linked list
	ListNode* temp=(ListNode*)malloc(sizeof(ListNode));
	temp->data=d;
	temp->next=NULL;
	return temp;
}

void display(ListNode* head){ //displaying linked list
	ListNode* current=head; // current node set to head

	printf("displayig the converted list...\n");
	while(current!=NULL){ //traverse until current node isn't NULL
	    if(current->next)
		printf("%d->",current->data);
		else
		printf("%d->NULL\n",current->data);
		current=current->next; // go to next node
	}
}
   
ListNode* temp; //global temp variable   
bool checkPalindrome(ListNode* p){ //recursive function to check for palindrome
        if(p==NULL)
            return true;
        bool result=checkPalindrome(p->next) & (temp->data==p->data);
        temp=temp->next;
        return result;
}
    
    
bool isPalindrome(ListNode* head) { //functio to check for palindrome
        temp=head;
        return checkPalindrome(head);
}

int main(){
	printf("creating the linked list by inserting new nodes at the end\n");
	printf("enter 0 to stop building the list, else enter any integer\n");
	int k;
	ListNode* curr,*temp;
	cout<<"enter list to check whether palindrom...\n";
	scanf("%d",&k);
	ListNode* head=creatnode(k); //buliding list, first node
	scanf("%d",&k);
	temp=head;

	///////////////////inserting at the end//////////////////////
	while(k){
		curr=creatnode(k);
		temp->next=curr;//appending each node
		temp=temp->next;
		scanf("%d",&k);
	}
	cout<<"displaying list1...\n";
	display(head); // displaying the list
	if(isPalindrome(head))
		cout<<"Palindrome list\n";
	else
		cout<<"Not palindrome\n";
	
	return 0;
}

Output

First run:
enter 0 to stop building the list, else enter any integer
enter list to check whether palindrom...
1 2 2 1 0
displaying list1...
displayig the converted list...
1->2->2->1->NULL
Palindrome list

Second run:
enter 0 to stop building the list, else enter any integer
enter list to check whether palindrom...
1 2 3 2 0
displaying list1...
displayig the converted list...
1->2->3->2->NULL
Not palindrome