Leetcode 234:回文链接列表

Leetcode 234: Palindrome LinkedList(Leetcode 234:回文链接列表)

本文介绍了Leetcode 234:回文链接列表的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在寻找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:回文链接列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:Leetcode 234:回文链接列表

基础教程推荐