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

Posted on

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s