O(n) time & O(1) heap space without reversing list


  • 0
    M

    This recursive solution runs in O(n) time and O(1) heap space. However it uses O(n) stack space for the recursive calls. As another user pointed out, it is impossible to achieve O(1) space.

    public class Solution {
        private class BooleanWrapper{
            boolean isPalindrome;
            ListNode next;
            
            BooleanWrapper(boolean isPal, ListNode next) {
                this.isPalindrome = isPal;
                this.next = next;
            }
        }
        
        public boolean isPalindrome(ListNode head) {
            int len = getLength(head);
            if(len == 1) {
                return true;
            }
            
            return isPalindromeHelper(head, len).isPalindrome;
        }
        
        private BooleanWrapper isPalindromeHelper(ListNode head, int len) {
            if(len == 0) {
                return new BooleanWrapper(true, head);
            }
            
            if(len == 1) {
                return new BooleanWrapper(true, head.next);
            }
            
            BooleanWrapper internal = isPalindromeHelper(head.next, len - 2);
            return new BooleanWrapper(internal.isPalindrome && head.val == internal.next.val, internal.next.next);
        }
        
        private int getLength(ListNode head) {
            int len = 0;
            while(head != null) {
                head = head.next;
                len++;
            }
            
            return len;
        }
        
    }
    

Log in to reply
 

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