Redirecting to
NADOS

Is Linked List A Palindrome?

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
2. You are required to complete the body of IsPalindrome function. The function is expected to check if the linked list is a palindrome or not and return true or false accordingly.
3. Input and Output is managed for you.
Input Format 
Input is managed for you
Output Format 
Output is managed for you
Question Video
Constraints 
1. Time complexity -> O(n)
2. Space complexity -> Recursion space, O(n)
Sample Input 
5
1 2 3 2 1
Sample Output 
true


  • Editorial

    The problem deals with checking whether the given list is a palindrome or not. A list is a palindrome when there is no difference in iterating the list either from start to end or vice-versa.

    To check for the palindrome, we need to compare the first node with the last node, similarly, the second node with the second last node, and so on. We can achieve this with the help of recursion by traversing the list till we reach the base case, this ensures that we are at the end of the linked list. Now we keep a global variable which points at the head. Comparing global variable and last node, if true, then we update the global variable to next node, and returning from function ensures that we go back to the previous node, and if false then irrespective of future comparisons the list can not be palindromic hence non-palindromic.

    Recursion Flow:


    Below is the implementation in Java: 

    private boolean IsPalindromeHelper(Node right){
                                    if(right == null){
                                    return true;
                                    }
                                    boolean rres = IsPalindromeHelper(right.next);
                                    if(rres == false){
                                    return false;
                                    } else if(pleft.data != right.data){
                                    return false;
                                    } else {
                                    pleft = pleft.next;
                                    return true;
                                    }
                                } 
                                Node pleft;
                                public boolean IsPalindrome(){
                                    pleft = head;
                                    return IsPalindromeHelper(head);
                                }

    java false

    Time Complexity: O(n)

    The time complexity for the function is linear as we are traversing on every node.

    Space Complexity: O(n)

    The space complexity for the function is linear as we have n function calls hence we have consumed a linear space in the recursion stack.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name