Check if the Singly Linked List is a Palindrome-Interview Problem

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?