Recursive O(n) Solution / No List Reversal / Easy to understand Java Solution with comments.


  • 0
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head==null){
                return true;
            }
            //Pass two copies in an array. One pointer we keep incrementing till the end.
            ListNode[] ptrs=new ListNode[2];
            ptrs[0]=head;
            ptrs[1]=head;
            return checkPalindrome(ptrs);
        }
        
        public boolean checkPalindrome(ListNode[] ptrs){
            ListNode back=ptrs[1],front=null;
            //End of the list has reached.
            if(back.next==null){
                front=ptrs[0];
                if(back.val==front.val){
                    //Increment the front pointer by 1 step
                    ptrs[0]=ptrs[0].next;
                    return true;
                }
            }else{
                //Increment the back pointer by 1 step and pass to the recursive call.
                //Keep a copy of the back pointer received in this function call
                ptrs[1]=back.next;
                if(checkPalindrome(ptrs)){
                    if(ptrs[0].val==back.val){
                        ptrs[0]=ptrs[0].next;
                        return true;
                    }
                }
            }
            return false;
        }
    }

Log in to reply
 

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