Accepted Java O(n) time O(1) space without reversing the list


  • 0
    A
    public class Solution {
        ListNode head;
        public boolean isPalindrome(ListNode head) {
            this.head=head;
            return reverse(head);
        }
        private boolean reverse(ListNode tail) {
            if(tail!=null){
                if(reverse(tail.next) && head.val==tail.val){
                    head=head.next;
                    return true;
                }
                return false;
            }
            return true;
        }
    }
    

    So I have tried to apply the same logic that is commonly used to determine if a string is a palindrome. i.e. maintain two pointers - one moves forward from the first value and other moves backward from the last value.
    To achieve this, I created a class variable 'head' that is my forward moving pointer and 'reverse' method parses the list backward.
    This works, however I am not sure if creating a class variable to achieve this can be considered as a good programming practice.
    I would appreciate if anybody has any thoughts/comments about this.


Log in to reply
 

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