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屋！