vSPARROW

leetcode : 234. Palindrome Linked List : memory usage beats 98.70 % of javascript submissions

Posted on June 19, 2020

Another memory success for one of my leetcode solutions

When reading the variables sonic and tails, remember the game, Sonic is always faster than Tails, which is why hes one step ahead.

//isPalindrome      - base function 
//getLength         - helper function
//reverseFromMiddle - helper function

//get Length of Linked List
const getLength = head => {
    let counter = 0
    while(head){
        head = head.next
        counter++
    }
    return counter
}

const reverseFromMiddle = (head,middleIndex)=>{
    let middleHead=null
    for(i=1;i<=middleIndex;i++){ //1 because head is already the first node
        head = head.next
    }
    // console.log(`reverseFromMiddle head is ${head.val}`)
    let sonic = head.next
    let tails = head
    tails.next = null
    while(sonic){
        let temp =tails
        tails=sonic
        sonic=sonic.next
        tails.next =temp
    }
    // console.log(`sonic is ${sonic}`)
    // console.log("tails is", tails)
    return tails
}

var isPalindrome = function(head) {
    //if we get an empty node counts as valid palindrome
    if(!head){return true} 
    //get the length of the Linked List
    let length = getLength(head);
    //calculate 1/2 point of node
    let middleIndex = ~~(length/2)
    //from 1/2 point of Linked List 
    // start reversing into a reversed Link List
    let middleHead = reverseFromMiddle(head,middleIndex)
    //compare 2 havles
    while(head && middleHead){
        if(head.val != middleHead.val){return false}
        head = head.next
        middleHead=middleHead.next
    }
    return true
};

runtime beats 55.40 % of javascript submissions