Check if a Singly Linked List is a Palindrome-Interview Problem
Difficulty: Medium
Asked in: Amazon, Microsoft, Adobe, Flipkart
Understanding the Problem:
Given a singly Linked List, you have to find out whether the linked list is a palindrome or not. A palindrome is nothing but a string or number which is same whether you read it from right to left or left to right. It is like the string and its mirror image both are same.
For example,
Input: 1->2->2->1->NULL
Output: Yes
Input: 7->7->7->NULL
Output: Yes
Input: 1->2->3->NULL
Output: No
Possible follow-up questions to ask the interviewer: →
- Is the data value of the given Linked List is only numbers? ( Ans : No, the data values can be anything.)
Linked List’s Node Class
class ListNode
{
int data
ListNode next
}
Solutions
We are going to discuss three different ways to approach this problem. Also, we will be writing the pseudo-codes for all the three possible solutions.
- Solution Using Stack: Here we will be using the stack data structure. Stack has a property that the element inserted first will be taken out last. This property will help us to find whether the given Linked List is palindrome or not.
- Solution By Reversing the Second Half: By reversing the second half, and making a little observation we can solve this problem easily.
- Solution with Recursion: We will here make use of recursion stack in a much smarter way to find our solution.
Solution Using Stack
Solution idea
The idea is very simple and straight-forward, we all know that stack is based on FILO(First In Last Out) principle. We will keep pushing all the elements of Linked List into the stack and once the linked list is fully traversed we will start popping the elements out of the stack and comparing with the linked list’s elements.
For better understanding the approach, let’s see an explanation : →
Given Linked List is : 1->2->2->1->NULL
Initially, our stack S is empty, we will start pushing elements of the linked list one after the other:
S = 1 (pushing 1)
S = 1 2 (pushing 2)
S = 1 2 2 (pushing 2)
S = 1 2 2 1 (pushing 1)
Now we will start popping an element out of the stack and comparing it with the linked list’s data starting from the head.
1(S.top) == 1(Linked List’s head)
2(S.top) == 2(Linked List’s head.next)
Similarly, if all the elements from both stack and linked list get matched as in this case, we can conclude that the linked list is a palindrome.
Solution steps
- We will create a stack S and push all the elements of the Linked List into the stack.
- Then we will pop the elements one by one from the stack and compare it with the data present in the Linked List sequentially.
- If there is any mismatch in comparison, we can conclude that the Linked List is not a palindrome else it is a palindrome.
Pseudo-code
boolean isListPalindrome(ListNode head)
{
// if the linked list is empty or having only one node
if(head == NULL or head.next == NULL)
return True
stack <List Datatype> S
ListNode temp = head
// traversing the linked list and pushing the elements into stack
while(temp is not NULL)
{
S.push(temp.data)
temp=temp.next
}
temp = head
// again traversing the linked list to compare
while(temp is not NULL)
{
topOfStack = S.top()
S.pop()
if(topOfStack is not equal temp)
return False
temp=temp.next
}
return True
}
Complexity Analysis
Time Complexity : O(L), where L is the length of the given linked list.
Space Complexity: How much extra space used? ( Think! )
Critical ideas to think!
- Take an example of palindrome, divide the palindrome into two equal parts. Reverse the second half of the palindrome. Have you got any observation?
Solution By Reversing the Second Half
Solution idea
We will divide our Linked List into two halves by finding the middle node. When we reverse the second half of the Linked List and if the Linked List is a palindrome then the second half becomes exactly same to the first half of the Linked List. This solution is based on this idea.
Solution steps
- We will first find the middle node of the given Linked List(Consider both the odd and even cases).
- Then, we will reverse the second half of the Linked List.
- We will compare the second half with the first half, if both the halves are exactly the same then the linked list is a palindrome.
- Reconstruct the actual given Linked List by again reversing the second half and attaching it to the first half.
Pseudo-code
boolean compareList(firstHalf , secondHalf)
{
while(firstHalf is not NULL and secondHalf is not NULL)
{
if(firstHalf.data is not equal secondHalf.data)
return False
firstHalf = firstHalf.next
secondHalf = secondHalf.next
}
return True
}
ListNode reverseList(ListNode head)
{
if(head is NULL or head.next is NULL)
return head
ListNode reversedPart = reverseList(head.next)
head.next.next = head
head.next = NULL
return reversedPart
}
boolean isListPalindrome(ListNode head)
{
ListNode midNode = NULL
ListNode slow_pointer = head
ListNode previous_of_mid = NULL
ListNode fast_pointer = head.next
if(head is not NULL and head.next is not NULL)
{
while(fast_pointer is not NULL and fast_pointer.next is not NULL)
{
fast_pointer = fast_pointer.next.next
previous_of_mid = slow_pointer
slow_pointer = slow_pointer.next
}
if(fast_pointer is not NULL) //If there are odd nodes
{
midNode = slow_pointer
slow_pointer = slow_pointer.next
}
ListNode secondHalf = slow_pointer
ListNode reversedHalf = reverse(secondHalf)
boolean result = compareList(head, reversedHalf)
}
}
Complexity Analysis
Time Complexity: O(N), where N is the length of the Linked List
Space Complexity : O(N) (Why? Can you reduce this complexity?)
Critical ideas to think!
- You must have got the idea of how to reduce the space complexity(Think if not). Learn more about the algorithm used here to find the middle node.
Solution Using Recursion
Solution idea
This solution uses the recursion call stack in a very efficient way. We will take two pointers, one for the leftmost node and the other one for the rightmost node. We will check if the data of the left and the right nodes matches or not. If there is a match, we will go on recursively to check for the rest of the list. At last, if all the calls return true (that conveys match), we can conclude that the given Linked List is a palindrome.
Solution steps
- Recursively traverse the entire linked list to get the last node as a rightmost node.
- Compare the first node (left node) with the right node. If both are having same data value then recursively call for the sub-list as to check if the sub-list is a palindrome or not.
- If all the recursive calls are returning true, it means the Linked List given is a palindrome else it is not a palindrome.
Pseudo-code
boolean isListPalindrome(ListNode &leftmostNode, ListNode rightmostNode)
{
if(rightmostNode == NULL)
return True
//check if the sub-list is a palindrome
boolean resultSublist = isListPalindrome(leftmostNode, rightmostNode.next)
if(resultSublist is False) //No need to check then
return False
boolean result = leftmostNode.data == rightmostNode.data
leftmostNode = leftmostNode.next
return result
}
Complexity Analysis
Time Complexity : O(N)
Space Complexity: O(N) (Stack space)
Critical ideas to think!
- Try to understand the recursion call stack for this solution and getting a clear understanding of how recursion works.
- Here we have passed the left node pointer variable as a reference. Why?
Comparison of different Solutions
Suggested Problems to Solve
- Sum of the values present in the nodes of the Linked List.
- Convert a Linked List into an array.
- Check if the given Linked List is sorted or not.
- Convert a Circular Linked List into a Singly Linked List.
Happy Coding! Enjoy Algorithms!!