解題 35. Palindrome Linked List

16 2 月, 2022 欣迪

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, 10⁵].
0 <= Node.val <= 9

這題卡關超久，一開始用了字串的解法。

/**
 * 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) {
    let current = ''
    let reverse = ''
    let node = head
    while(node) {
        current += node.val
        reverse =  node.val + reverse
        node = node.next
    }
    return current === reverse
};

但這種解決方式有很大的問題，由於這題限定 Node 的 val 是 0 到 9 之間，因此每次只會增加一個字元。所以在這個狀態下可以過關。

但是，如果題目的難度提， val 可以是十位數，例如一個 [1, 21] 的 NodeList。 function 會判斷 121 === 121 給一個 true 的錯誤解答。

看了幾次討論區後，覺得最合理的解法如下：

**
 * 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) {
    let current = head
    const sameAsLast = (_node) => {
        if (!_node) return true
        const isLast = sameAsLast(_node.next)
        if (isLast && _node.val === current.val) {
            current = current.next
            return true
        } else {
            return false
        }
    }
    return sameAsLast(head)
};

這個我花了不少時間理解，這邊逐步解說：