欣迪

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

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

/**
 * 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)
};

這個我花了不少時間理解,這邊逐步解說:

首先我們必須要將起始的 node 存起來,範例的變數是 current。

這時候我們用遞迴的方式去判斷,直接衝到最後面一個 node。 並比較最後一個 node 的 val 和 current 的 val 是否相同。

如果 current.val === node.val 那麼這個遞迴函數要回傳 true。

回傳之前,先把 current 往下移動一格,讓上一層遞迴 node.val 能對比到對應的 current 並一路往回傳。

如果回傳失態,遞迴會將失敗的結果一路往前回傳,得到 false 的答案。

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。