Quick Javascript Implementation


  • 0
    J

    I think I have a relatively efficient solution in Javscript here. I think the way I'm finding the 'middle' is relatively clever.

    I'm not sure if it would qualify as O(n) time though (I'm a little weak on calculating Big O)? It basically .nexting through every item in the list to get the middle, .5n to reverse and then (potentially) another time to compare, wouldn't that be O(2.5n).

    var isPalindrome = function(head) {
        if(head === null) return true;
        if(head.next === null) return true;
        
        var slowptr = head;
        var fastptr = head;
        var leftptr = head;
        var rightptr;
        
        while(fastptr && fastptr.next) {
            slowptr = slowptr.next;
            fastptr = fastptr.next;
            if(fastptr && fastptr.next) fastptr = fastptr.next;
        }
        
        rightptr = reverse(slowptr);
        
        while(rightptr) {
            if(rightptr.val != leftptr.val) return false;
            leftptr = leftptr.next ? leftptr.next : null;
            rightptr = rightptr.next ? rightptr.next : null;
        }
        return true;
     };
     
     var reverse = function(head){
         var current = head;
         var next;
         var prev;
         
         while(current) {
             next = current.next;
             current.next = prev;
             prev = current;
             current = next;
         }
         
         return prev;
     }

Log in to reply
 

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