Without reversing, In O(N) time and O(1) space - A different approach


  • 0
    H

    Idea: I get to middle of the list, then I recurse to the end from mid and compare with the first half of the list using returnedN1, if values are unequal null is passed back from my helper method. Recursive stack serves the purpose of reversing the half list.

    class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null) return true;
            ListNode mid = head, fast = head;
            
            while(fast!=null && fast.next!=null){
                fast = fast.next.next;
                mid = mid.next;
            }
            if(fast != null) mid = mid.next;
            
            ListNode result = isPalindrome(head, mid);
            if(result==null) return false;
            return true;
        }
        private ListNode isPalindrome(ListNode n1, ListNode n2){
            if(n2 == null) return n1;
            ListNode returnedN1 = isPalindrome(n1, n2.next);
            
            if(returnedN1 == null || n2.val != returnedN1.val) return null;
            return returnedN1.next;
        }
    }
    

  • 0
    F

    @hihihahahoho I don't think this can be considered O(1) space because recursive calls consume space in the stack. At the greatest depth of your recursion, there are O(0.5n) calls on the stack, which reduces to O(n) space. I really don't think it's possible to solve this in O(1) space without doing worse than O(n) time.


Log in to reply
 

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