[力扣題解]：234. 回文連結清單

題目要求

請判斷一個連結清單是否為回文連結清單。

示例 1:

輸入: 1->2

輸出: false

示例 2:

輸入: 1->2->2->1

輸出: true

進階：

你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題？

解題思路

• 尋找回文串要從中間向兩側延伸，判斷回文串則要從兩端向中間周遊

1.雙指針判斷回文字元串

• 字元串為數組型順序存儲，可快速索引到字元串兩端，故采用雙指針

def isPalindrome(s):
    left = 0
    right =len(s)-1
    while (left < right) :
        if (s[left] != s[right])
            return false;
        left+=1
        right-=1
    return true

           

2.單連結清單的反向周遊

• 顯然，隻要可以實作單連結清單的反向周遊，便可實作和雙指針相似的效果
• 最簡單辦法是由反轉連結清單将反轉後的連結清單存入數組或新的連結清單，也可以利用遞歸

def traverse(head):
    if head == None:
    	return
    traverse(head.next)
    // 後序周遊代碼
    print(head.val)

           

3.判斷回文串

• 稍作修改便可實作

def traverse(right):
    if right== None:
    	return True
    res=traverse(right.next) and (left.val==right.val)
    left=left.next
    return res
    	
def isPalindrome(head):
    left = head
    return traverse(head)
           

4.進階

• 雖然我們實作了判斷回文串，但由于遞歸操作實際上是堆棧操作，空間複雜度為O(n)，故需要采取其他方式降低空間複雜度

a.快慢指針找到中間節點

slow=head
fast=head
if(fast and fast.next):
	slow=slow.next
	fast=fast.next.next
           

• 若長度為奇數，則增加一步操作

if fast:
	slow=slow.next
           

b.反轉中間節點後的連結清單

• 利用反轉連結清單我們就可以得到兩端的指針

  

c.從兩端向中間周遊

• 至此，結合以上三步，便可降低空間複雜度為O(n)

def isPalindrome(head: ListNode) -> bool:
        if head.next==None:
            return True
        slow=head
        fast=head
        left=head
        if (fast and fast.next):
            slow=slow.next
            fast=fast.next.next
        if fast!=None:
            slow=slow.next
        right=reverse(slow)
        while(right!=None and left!=None):
            if right.val!=left.val:
                return False
            right=right.next
            left=left.next
        return True
    def reverse(head):
        if head==None:
            return head
        if head.next==None:
            return head
        last=reverse(head.next)
        head.next.next=head
        head.next=None
        return last
           

參考資料

labuladong的算法小抄

234. 回文連結清單 - 力扣