LeetCode Notes: Palindrome Linked List

#leetcode

Question

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]

Output: true

Example 2:

Input: head = [1,2]

Output: false

Constraints:

  • The number of nodes in the list is in the range [1, 105].
  • 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Solution

Analysis:

  1. First convert the linked list into an array, and then judge whether the array is a palindrome array
  2. Loop this array to determine whether the values after moving the same distance from the start and end positions are the same. If they are all the same, the result is a palindrome linked list. If any set of values is different, it is not a palindrome linked list

Code:

/**
  * Definition for singly-linked list.
  * function ListNode(val, next) {
  * this.val = (val===undefined? 0: val)
  * this.next = (next===undefined? null: next)
  *}
  */
/**
  * @param {ListNode} head
  * @return {boolean}
  */
var isPalindrome = function(head) {

     // The linked list is converted to an array
     const transformList = []
     // Store the current node
     let currentNode = head

     // The value of each node is stored in the array
     while(currentNode != null){
         transformList.push(currentNode.val)
         currentNode = currentNode.next
     }

     // Loop to half of the position
     for(let i = 0; i <(transformList.length-1) / 2; i++){

         // Comparing the values at the same position before and after, if any pair of values is different, it is not a palindrome array
         if(transformList[i] !== transformList[transformList.length-i-1]){
             return false
         }
     }

     return true

};

Reference

Comments