題目

給你一個(gè)單鏈表的頭節(jié)點(diǎn) head，請(qǐng)你判斷該鏈表是否為回文鏈表。如果是，返回 true；否則，返回 false。

示例 1：

• 輸入：head = [1,2,2,1]
• 輸出：true

示例 2：

• 輸入：head = [1,2]
• 輸出：false

方法一：將值復(fù)制到數(shù)組中并判斷數(shù)組中元素個(gè)數(shù)

思路

如果你還不太熟悉鏈表，下面有關(guān)于列表的概要講述。

有兩種常用的列表實(shí)現(xiàn)，分別為數(shù)組列表和鏈表。如果我們想在列表中存儲(chǔ)值，它們是如何實(shí)現(xiàn)的呢？

• 數(shù)組列表底層是使用數(shù)組存儲(chǔ)值，我們可以通過(guò)索引在 的時(shí)間訪問(wèn)列表任何位置的值，這是由基于內(nèi)存尋址的方式。
• 鏈表存儲(chǔ)的是稱為節(jié)點(diǎn)的對(duì)象，每個(gè)節(jié)點(diǎn)保存一個(gè)值和指向下一個(gè)節(jié)點(diǎn)的指針。訪問(wèn)某個(gè)特定索引的節(jié)點(diǎn)需要 的時(shí)間，因?yàn)橐ㄟ^(guò)指針獲取到下一個(gè)位置的節(jié)點(diǎn)。

確定數(shù)組列表是否回文很簡(jiǎn)單，我們可以使用雙指針?lè)▉?lái)比較兩端的元素，并向中間移動(dòng)。一個(gè)指針從起點(diǎn)向中間移動(dòng)，另一個(gè)指針從終點(diǎn)向中間移動(dòng)。這需要 的時(shí)間，因?yàn)樵L問(wèn)每個(gè)元素的時(shí)間是 ，而有 個(gè)元素要訪問(wèn)。

然而同樣的方法在鏈表上操作并不簡(jiǎn)單，因?yàn)椴徽撌钦蛟L問(wèn)還是反向訪問(wèn)都不是 。而將鏈表的值復(fù)制到數(shù)組列表中是 ，因此最簡(jiǎn)單的方法就是將鏈表的值復(fù)制到數(shù)組列表中，再使用雙指針?lè)ㄅ袛唷?/p>

算法

一共為兩個(gè)步驟：

1. 復(fù)制鏈表值到數(shù)組列表中。
2. 使用雙指針?lè)ㄅ袛嗍欠駷榛匚摹?/li>

第一步，我們需要遍歷鏈表將值復(fù)制到數(shù)組列表中。我們用 currentNode 指向當(dāng)前節(jié)點(diǎn)。每次迭代向數(shù)組添加 currentNode.val，并更新 currentNode = currentNode.next，當(dāng) currentNode = null 時(shí)停止循環(huán)。

第二步，我們?cè)谄瘘c(diǎn)放置一個(gè)指針，在結(jié)尾放置一個(gè)指針，每一次迭代判斷兩個(gè)指針指向的元素是否相同，若不同，返回 false；相同則將兩個(gè)指針向內(nèi)移動(dòng)，并繼續(xù)判斷，直到兩個(gè)指針相遇。

代碼

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        if nil == head {
            return false
        }
        var vals: [Int] = []
        var currentNode: ListNode? = head
        while nil != currentNode {
            vals.append(currentNode!.val)
            currentNode = currentNode!.next
        }
        
        var i = 0
        while i < (vals.count / 2) {
            if vals[i] != vals[vals.count - 1 - i] {
                return false
            }
            i += 1
        }
        return true
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：，其中 指的是鏈表的元素個(gè)數(shù)。

  • 第一步： 遍歷鏈表并將值復(fù)制到數(shù)組中，。
  • 第二步：雙指針判斷是否為回文，執(zhí)行了 次的判斷，即 。
  • 總的時(shí)間復(fù)雜度：。

• 空間復(fù)雜度：，其中 指的是鏈表的元素個(gè)數(shù)，我們使用了一個(gè)數(shù)組列表存放鏈表的元素值。