題目:

Given the head of a singly linked list, return true if it is a palindrome.

給定一個linked list,判斷它是否對稱

這題我並沒有什麼頭緒,於是採取了最笨的做法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        record=[]
        while head:
            record.append(head.val)
            head=head.next
        
        for i in range(len(record)//2):
            if record[i]!=record[-1-i]:
                return False
            
        return True

將linked list所有值紀錄到陣列內
再前後比較陣列值是否相等來決定該linked list是否對稱
雖然陽春,但效率不會到太差
最後執行時間784ms(faster than 95.31%)

當然這種解法是不能瞞混過關的
題目隨即說了一句

Follow up: Could you do it in O(n) time and O(1) space?

想不到不用額外空間解的我只好去看討論區
結果就看到了下面的解法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast=head
        slow=head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            
        pre=None
        while slow:
            temp=slow.next
            slow.next=pre
            pre=slow
            slow=temp
            
        l=head
        r=pre
        while r:
            if l.val!=r.val:
                return False
            l=l.next
            r=r.next
        return True

設立fast跟slow兩個指標,一個一次走兩步,一個一次走一步
直到fast走到底為止
此時可以發現slow會在linked list近中央的位置
將slow之後的linked list全數反轉(pre剛好會是反轉後的頭)
這時我們只要一個指標從head開始,一個指標從pre開始
就能比較值來決定該linked list是否對稱了
最後執行時間796ms(faster than 94.00%)

那我們下題見