Leetcode 234：回文鏈接列表 [英] Leetcode 234: Palindrome LinkedList

問題描述

我正在尋找234. Palindrome Linked List的解決方案：

給定單鏈表的head，如果它是回文，則返回true。

這是正確的解決方案：

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        #Null condition
        if head == None:
            return True
        
        #move fast and slow pointers
        s_p = head
        f_p = head
        while(f_p.next != None and f_p.next.next != None):
            s_p = s_p.next
            f_p = f_p.next.next
            
        #reverse slow pointer
        first_half = self.reverse(s_p)     
        
        #compare
        while(first_half != None and head != None):
            print(first_half.val)
            print(head.val)
            if(first_half.val != head.val):
                return False
            first_half = first_half.next
            head = head.next
        
        return True
    
    def reverse(self,c_p):
        
        prev_head = None
        
        while(c_p != None):
            temp = c_p.next
            c_p.next = prev_head
            prev_head = c_p
            c_p = temp
        
        return prev_head

但我很難理解該代碼為什么會起作用。

示例：1->；2-->；1

根據這個YouTube video的想法是，我們取列表的前半部分，將其顛倒過來，然后進行比較。

該插圖顯示，我們將在反轉后將指向1-&>2；->Null的指針與另一個為1-&>Null的指針進行比較。

雖然在我看來，這實際上是將上半年：1-&>；2->Null與 Head：1->；2->；空。

此代碼確實通過了所有測試用例，但我預計第二個代碼(我的修改版本)也應該可以工作，但它不能：

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        #Null condition
        if head == None:
            return True
        
        #move fast and slow pointers
        s_p = head
        f_p = head
        while(f_p.next != None and f_p.next.next != None):
            s_p = s_p.next
            f_p = f_p.next.next
        
        #set s_p.next to Null
        s_p.next = None

        #reverse fast pointer
        second_half = self.reverse(f_p)
        
     
        
        #compare
        while(second_half != None and head != None):
            print(second_half.val)
            print(head.val)
            if(second_half.val != head.val):
                return False
            second_half = second_half.next
            head = head.next
        
        return True
    
    def reverse(self,c_p):
        
        prev_head = None
        
        while(c_p != None):
            temp = c_p.next
            c_p.next = prev_head
            prev_head = c_p
            c_p = temp
        
        return prev_head

這樣，我所要做的就是將第二個指針：2->1->Null反轉為1-&>2-&>Null

現在我們可以將頭部與反轉的下半部進行比較。

它沒有通過LeetCode中的測試，但我很困惑為什么不能。

我知道這是一個簡單的問題，但我仍然在努力。

非常感謝您的幫助。

推薦答案

您修改的版本中有一個錯誤
您的邏輯是正確的，但是當您的反向函數被定義為從參數PASS反轉列表時，f_p將指向最后一個元素，而不是中間元素。
Leetcode版本解決方案將起始值與反轉后半部分的值進行比較。

這篇關于Leetcode 234：回文鏈接列表的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持IT屋！