Solution by rohitnandi12


  • 2
    R

    Primary Thoughts

    What is a Palindrome?

    A word, phrase, or sequence that reads the same backwards as forwards, e.g. "madam" or "nurses run"
    With respect to linked list example of palindrome will be "1->2->1" and not a palindrome will be "1->2->3".

    Test Cases

    Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.

    T1 : [1,2,3,4,3,2,1]     // true
    T2 : [1,2,3,3,2,1]       // true
    T3 : [1,1]               // true
    T4 : []                  // true
    T4 : [1,2,3,4,2,1]       // false
    
    

    Various Approaches

    Approach #1

    Using a stack. In first traversal, push all the elements in stack. Traverse the list again, this time pop one element and compare it with the current list element, repeat until both the elements are equal. Time Complexity O(n), Space Complexity O(n).

    Approach #2

    Using Recursion. Idea is the same as above, but in this approach functional call stack is used as a container. Recursively traverse to the end of the list, when end is reached, traverse back and compare the last node with first node and so on.

    Java

    class Solution {
        private ListNode left = null;
        public boolean isPalindrome(ListNode head) {
            this.left = head;
            return isPalindromeUtil(head);
            
        }
        private boolean isPalindromeUtil(ListNode right) {
            
            /* stop recursion when pointer goes beyond List length */
            if(right==null)return true;
            
            /* Check If sub-list is palindrome or not.*/
            boolean isRestPallin = isPalindromeUtil(right.next);
            if(!isRestPallin)return false;
            
            boolean isCurrentMatch = (left.val == right.val);
            
            left = left.next;
            
            return isCurrentMatch;   
        }
    }
    
    **Complexity Analysis**
    
    * Time complexity : $$O(n)$$
    
    * Space complexity : $$O(1)$$. If functional call stack is neglected.
    
    
    

    Approach #3 Reversing the linked list [Accepted]

    Algorithm

    • Use two pointer to reach the half of the list.
    • Reverse the second half of the list
    • compare the first and the new reversed half of the list
    • if both are exactly equal it is a palindrome

    Java

    class Solution {
        public boolean isPalindrome(ListNode head) {
    
            ListNode fast = head;
            ListNode slow = head;
    
            while(fast!=null && fast.next!=null){
                fast = fast.next.next;
                slow = slow.next;
            }
    
            slow = reverseList(slow);
            fast = head;
            while(slow!=null && slow.val==fast.val){
                slow = slow.next;
                fast = fast.next;
            }
    
            return slow==null;
        }
        private ListNode reverseList(ListNode node){
    
            if(node == null)return null;
            if(node.next == null)return node;
    
            ListNode temp = reverseList(node.next);
            node.next.next = node;
            node.next = null;
    
            return temp;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$

    • Space complexity : $$O(1)$$
      Only downfall to this approach is the actual list is modified.If the input is read-only this approach is
      not applicable.

    ** Thank You.. Happy Coding :)**


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.