Python链表不能保存head nod

Question

这是关于一个leetcode问题：“234。“回文链表”

我想反转链表，并将反转后的链表与原始链表进行比较。如果没有差异，则返回True。你知道吗

但奇怪的是，虽然我复制了一个虚拟节点的头部，以记录开始的位置。反转列表后，我无法从虚拟节点进行迭代，似乎列表中只剩下1个元素。你知道吗

为什么/如何更新虚拟节点？这让我很烦，我想把头撞到墙上。你知道吗

感谢您的帮助！你知道吗

谢谢！你知道吗

基于我有限的知识，我已经尽力了。你知道吗

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """


        dummy = head
        prev = None

        while head:
            temp = head
            head = head.next
            temp.next = prev
            prev = temp  

        while prev and dummy:
            print prev.val, dummy.val

            if prev.val != dummy.val:
                return False

            prev = prev.next
            dummy = dummy.next

        return True

我希望上面的代码能正常工作

Answer 1

从你的代码，我认为你的想法是反向链接列表，并与原来的一个比较，但这是不正确的。因为你改变了原来的链接列表，你不能再做比较了，所以你必须复制一份，但这是一个低效的解决方案。你知道吗

我已经根据您的代码编辑了copy version，它可以工作，但不是最好的方法。你知道吗

def isPalindrome(self, head):
    dummy = head
    prev = None
    cur = origin = ListNode(0)

    # copy the original linkedlist
    while head:
        cur.next = ListNode(head.val)
        head = head.next
        cur = cur.next

    head = dummy
    while head:
        temp = head
        head = head.next
        temp.next = prev
        prev = temp

    cur = origin.next
    while prev and cur:
        print(prev.val, cur.val)

        if prev.val != cur.val:
            return False

        prev = prev.next
        cur = cur.next

    return True

更好的方法是反转LinkList的前半部分，比较前半部分是否等于后半部分：

def isPalindrome(self, head):
    if not head or not head.next:
        return True
    count, cur = 0, head
    while cur:
        cur = cur.next
        count += 1

    pre, cur, post = None, head, head.next
    for _ in range(count // 2):
        cur.next = pre
        pre, cur, post = cur, post, post.next
    head.next = cur

    slow = pre
    fast = cur.next if count % 2 else cur

    for _ in range(count // 2):
        if slow.val != fast.val:
            return False
        slow, fast = slow.next, fast.next

    return True

更优雅的版本，但不是那么容易理解：

def isPalindrome(self, head):
    check = None
    slow = fast = head
    # traverse and reverse
    while fast and fast.next:
        fast = fast.next.next
        check, check.next, slow = slow, check, slow.next

    if fast:
        slow = slow.next
    while slow and slow.val == check.val:
        slow = slow.next
        check = check.next
    return not check

希望这对您有所帮助，如果您还有其他问题，请发表评论。：）