0

想知道我是否可以得到一些帮助。假设您正在尝试使用以下内容确定链表是否是回文：

 def isPalindrome(self, head: ListNode) -> bool:

        current, prev = head, None

        if not head:
            return False

        if not head.next:
            return True

        while current:
            nextnode = current.next
            current.next = prev
            prev = current
            current = nextnode
            print(current, prev)
            if current:
                if current == prev or current.next == prev:
                    return True
        return False

ListNode 定义为：

class ListNode():
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

这里的想法是开始重组反向列表并在每一步检查节点是否相等（或偶数节点的下一个节点相等）。在指向 1 -> 2 -> 2 -> 1 的示例 LL 上运行此代码会返回 false，但如果我们检查正在比较的对象：

ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}} ListNode{val: 1, next: None}
ListNode{val: 2, next: ListNode{val: 1, next: None}} ListNode{val: 2, next: ListNode{val: 1, next: None}}
ListNode{val: 1, next: None} ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}
None ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}

您可以在打印的输出中看到存在节点似乎返回相同结构列表的情况（第 2 行）。我假设比较失败是因为两个拆分列表的起点虽然是 2 -> 1，但在内存中是不同的 2 -> 1，因此比较失败？

如果我对失败原因的理解是正确的，有没有办法比较节点以使其工作（不超出 O(n) 运行时）？

PS我不想要不同的解决方案，我只是好奇是否有办法使这项工作:)

4

0 回答 0