ES6 solution; O(n) time, O(1), reversing first half


  • 0
    Y
    function getLength(head) {
      let node = head
      let length = 0
      while (node) {
        length += 1
        node = node.next
      }
      return length
    }
    
    function advanceToIndex(head, index) {
      let node = head
      let i = 0
      while (node && i < index) {
        i += 1
        node = node.next
      }
      return node
    }
    
    function reverseToIndex(head, index) {
      let prev = null
      let next = head
      let i = 0
      while (next !== null && i <= index) {
        const tempNext = next.next
        next.next = prev
        prev = next
        next = tempNext
        i += 1
      }
      return prev
    }
    
    // https://leetcode.com/problems/palindrome-linked-list/
    //
    // O(n) time palindromic linked list test
    function isPalindrome(head) {
      if (!head) {
        return true
      }
      const length = getLength(head)
      const mid = Math.floor(0.5 * length)
    
      // reverse the first half of the list
      const steps = mid - 1
      const tempJ = advanceToIndex(head, length % 2 === 0 ? mid: mid + 1)
      const tempI = reverseToIndex(head, steps)
    
      let i = tempI
      let j = tempJ
      while (i && j) {
        if (i.val !== j.val) {
          return false
        }
        i = i.next
        j = j.next
      }
      // reverse the first half of the list again
      reverseToIndex(tempI, steps)
      if (tempI) {
        tempI.next = tempJ
      }
      return true
    }
    

Log in to reply
 

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