請判斷一個鏈表是否為回文鏈表。

示例 1:

輸入: 1->2 輸出: false

示例 2:

輸入: 1->2->2->1 輸出: true

進階：
你能否用 O(n) 時間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

">

請判斷一個鏈表是否為回文鏈表。

示例 1:

輸入: 1->2 輸出: false

示例 2:

輸入: 1->2->2->1 輸出: true

進階：
你能否用?O(n) 時間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

快慢指針

我們可以將鏈表的后半部分反轉(zhuǎn)（修改鏈表結(jié)構(gòu)），然后將前半部分和后半部分進行比較。比較完成后我們應(yīng)該將鏈表恢復(fù)原樣。雖然不需要恢復(fù)也能通過測試用例，但是使用該函數(shù)的人通常不希望鏈表結(jié)構(gòu)被更改。

該方法雖然可以將空間復(fù)雜度降到 O(1)，但是在并發(fā)環(huán)境下，該方法也有缺點。在并發(fā)環(huán)境下，函數(shù)運行時需要鎖定其他線程或進程對鏈表的訪問，因為在函數(shù)執(zhí)行過程中鏈表會被修改。

整個流程可以分為以下五個步驟：

找到前半部分鏈表的尾節(jié)點。

反轉(zhuǎn)后半部分鏈表。

判斷是否回文。

恢復(fù)鏈表。

返回結(jié)果。

使用快慢指針在一次遍歷中找到：慢指針一次走一步，快指針一次走兩步，快慢指針同時出發(fā)。當(dāng)快指針移動到鏈表的末尾時，慢指針恰好到鏈表的中間。通過慢指針將鏈表分為兩部分。

若鏈表有奇數(shù)個節(jié)點，則中間的節(jié)點應(yīng)該看作是前半部分。

Code

class Solution:def findFirstHalfEnd(self, node):fast = slow = nodewhile fast.next is not None and fast.next.next is not None:fast = fast.next.nextslow = slow.nextreturn slowdef reverseList(self, node):previous, current = None, nodewhile current is not None:nextNode = current.nextcurrent.next = previousprevious = currentcurrent = nextNodereturn previousdef isPalindrome(self, head: ListNode) -> bool:# 判斷邊界情況if head is None:return True# 找到前半部分鏈表的為節(jié)點并反轉(zhuǎn)后半部分鏈表firstHalfEnd = self.findFirstHalfEnd(head)secondHalfStart = self.reverseList(firstHalfEnd.next)# 判斷是否為回文ans, firstPosition, secondPosition = True, head, secondHalfStartwhile ans and secondPosition is not None:if firstPosition.val != secondPosition.val:return FalsefirstPosition = firstPosition.nextsecondPosition = secondPosition.next# 還原反轉(zhuǎn)的鏈表firstHalfEnd.next = self.reverseList(secondHalfStart)return ans

復(fù)雜度分析

• 時間復(fù)雜度：$O(n)$，其中 $n$ 指的是鏈表的大小。

• 空間復(fù)雜度：$O(1)$。我們只會修改原本鏈表中節(jié)點的指向，而在堆棧上的堆棧幀不超過 $O(1)$。

總結(jié)

以上是生活随笔為你收集整理的234. Palindrome Linked List 回文链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。