检查链表是否为回文。

huangapple go评论59阅读模式
英文:

Check if the Linked List is Palindrome or not

问题

以下是你要翻译的代码部分:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverseLL(head):
    if head is None or head.next is None:
        return head
    rest = reverseLL(head.next)
    head.next.next = head
    head.next = None
    return rest

def checkpalindrome(head):
    temp = reverseLL(head)
    while head != None and temp != None:
        if temp.data != head.data:
            return False
        temp = temp.next
        head = head.next
    return True
英文:

When I try to check whether the linked list is palindrome or not, the following code gives me the error. My Approach is:
Step 1:- I am reversing the linked list (temp = reverseLL(head).
Step 2:- Checking elements of the reverse linked list to the original linked list.
Step 3:- Returning True if it is palindrome else False

But my code is not working for the input [1,1,2,1], it shows me the result is True.

class Node:
def __init__(self, data):
        self.data = data
        self.next = None

def reverseLL(head):
    if head is None or head.next is None:
        return head
    rest = reverseLL(head.next)
    head.next.next = head
    head.next = None
    return rest


def checkpalindrome(head):
    temp = reverseLL(head)
    while head != None and temp != None:
        if temp.data != head.data:
            return False
        temp = temp.next
        head = head.next
    return True

答案1

得分: 0

你可以将链表中的值创建成一个普通列表,然后将该列表与其反转版本进行比较。类似这样:

class Node:
    def __init__(self, n, next=None):
        self.n = n
        self.next = next

nums = [[1, 1, 2, 1, 1], [1, 1, 2, 1]]

def populate(nums):
    if nums:
        head = Node(nums[0])
        tail = head
        for n in nums[1:]:
            tail.next = Node(n)
            tail = tail.next
        return head
    return None

def ispalindrome(head):
    if head:
        values = [head.n]
        while head := head.next:
            values.append(head.n)
        return values == values[::-1]
    return False

for nl in nums:
    head = populate(nl)
    if ispalindrome(head):
        print(nl, 'is palindromic')
    else:
        print(nl, 'is not palindromic')

输出结果:

[1, 1, 2, 1, 1] is palindromic
[1, 1, 2, 1] is not palindromic
英文:

You could create a regular list out of the values in the linked list then simply compare that list with a reversed version of itself. Something like this:

class Node:
    def __init__(self, n, next=None):
        self.n = n
        self.next = next

nums = [[1, 1, 2, 1, 1], [1, 1, 2, 1]]

def populate(nums):
    if nums:
        head = Node(nums[0])
        tail = head
        for n in nums[1:]:
            tail.next = Node(n)
            tail = tail.next
        return head
    return None

def ispalindrome(head):
    if head:
        values = [head.n]
        while head := head.next:
            values.append(head.n)
        return values == values[::-1]
    return False

for nl in nums:
    head = populate(nl)
    if ispalindrome(head):
        print(nl, 'is palindromic')
    else:
        print(nl, 'is not palindromic')

Output:

[1, 1, 2, 1, 1] is palindromic
[1, 1, 2, 1] is not palindromic

答案2

得分: 0

问题是,当列表被反转时,head 节点变成了尾部,因此回文检查将比较反转后的列表与其自身的尾节点(该尾节点没有下一个节点)。

请注意,反转的列表并不创建一个新的列表。它只是将原始列表反转,因此没有更多的可能性以原始顺序遍历列表。

一个不需要 O(n) 辅助空间的解决方案是只反转列表的一半,然后您可以比较这两个部分。

以下是如何调整您的代码来实现这一点:

def checkpalindrome(head):
    return isPrefixLL(head, reverseLL(centerLL(head)))

def centerLL(head):  # 检索中间节点(或第二半的第一个节点)
    fast = slow = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def isPrefixLL(a, b):  # 这是您已经拥有的比较代码
    while a and b:
        if a.data != b.data:
            return False
        a = a.next
        b = b.next
    return True

您的 reverseLL 代码可以保持不变,尽管它使用了额外的堆栈空间。如果您真的想避免 O(n) 辅助空间,您应该将其改为迭代版本,这样也会运行得稍快一些:

def reverseLL(head):
    tail = None
    while head:
        head.next, tail, head = tail, head, head.next
    return tail
英文:

The problem is that when the list has been reversed, the head node has become the tail, and so the palindrome check will compare the reversed list with its own tail node (that has no next node).

Realise that the reversed list does not create a new list. It is the original list that has been reversed and so there is no more possibility to traverse the list in its original order.

A solution that does not need O(n) auxiliary space is to only reverse half of the list and then you can compare the two halves.

Here is how your code could be adapted to achieve that:

def checkpalindrome(head):
    return isPrefixLL(head, reverseLL(centerLL(head)))

def centerLL(head):  # Retrieve the middle node (or the first of second half)
    fast = slow = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def isPrefixLL(a, b):  # This is the comparison code you already had
    while a and b:
        if a.data != b.data:
            return False
        a = a.next
        b = b.next
    return True

Your reverseLL code can remain unchanged, although it uses extra stack space. If you really want to avoid O(n) auxiliary space, you should make it iterative -- which will also run slightly faster:

def reverseLL(head):
    tail = None
    while head:
        head.next, tail, head = tail, head, head.next
    return tail

huangapple
  • 本文由 发表于 2023年2月10日 15:32:40
  • 转载请务必保留本文链接:https://go.coder-hub.com/75408101.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定