題目描述
請(qǐng)判斷一個(gè)鏈表是否為回文鏈表剔难。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
進(jìn)階：
你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題贺纲？
解法
若要滿足 O(1) 空間復(fù)雜度，則不能借助于列表或棧結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)逛万。因?yàn)閱捂湵聿幌褡址梢赃M(jìn)行直接訪問，所以這里采用的方式為，找到單鏈表中間元素，并反轉(zhuǎn)單鏈表前半部分罢吃，然后與單鏈表后半部分進(jìn)行比較是否為回文結(jié)構(gòu)。
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow,fast,left=head,head,None
while fast and fast.next:
fast=fast.next.next
slow.next,left,slow=left,slow,slow.next
if fast:
slow=slow.next
while slow and slow.val==left.val:
slow,left=slow.next,left.next
return not slow
以 left 表示反轉(zhuǎn)后單鏈表前半部分的頭結(jié)點(diǎn)昭齐，第一個(gè) while 循環(huán)中找到鏈表中間節(jié)點(diǎn)刃麸，并逐步反轉(zhuǎn)鏈表節(jié)點(diǎn)，查找中間節(jié)點(diǎn)的方式為快慢兩個(gè)指針司浪，當(dāng)快指針為空時(shí)泊业，慢指針指向中間節(jié)點(diǎn)。第一個(gè)循環(huán)結(jié)束后啊易，left 為前半部分反轉(zhuǎn)鏈表的頭結(jié)點(diǎn)吁伺，slow 為后半部分鏈表的頭結(jié)點(diǎn)，因?yàn)殒湵碇泄?jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)租谈，slow 為中心節(jié)點(diǎn)篮奄，不需要參與回文判斷，所以第一個(gè)循環(huán)后割去，加 if 判斷窟却。第二個(gè)循環(huán)中判斷 left 和 slow 兩個(gè)鏈表的數(shù)據(jù)值是否一致。
此處采用反轉(zhuǎn)鏈表的方式呻逆，會(huì)修改原鏈表的結(jié)構(gòu)夸赫，因?yàn)橛涗浟?left 和 slow 指針，所以可以在判斷回文結(jié)構(gòu)后進(jìn)行恢復(fù)咖城，此處不再贅述茬腿。
