Python中的Palindrome链表具有O（1）额外空间

Question

这是＃234 Leetcode问题：

给定一个单链表，确定它是否是回文。

跟进：您能在O（n）时间和O（1）空间中做到吗？

O（n）空间很容易解决这个问题。但是，我不知道O（1）解决方案。我想到的唯一方法是使用递归：

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

class Solution(object):
    current = None

    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True

        self.current = head

        return self.compare(head)

    def compare(self, head):
        if not head: return True

        if not self.compare(head.next): return False

        if head.val != self.current.val:
            return False
        else:
            self.current = self.current.next
            return True

这适用于小样本，但给出

超过最大递归深度

任何人都可以仅使用O（1）空间来提供解决方案吗？谢谢。

Answer 1

如果允许您在适当位置修改列表，则可以执行以下操作：

1. 遍历列表以计算有多少个元素。
2. 第二次迭代，并从列表的中间开始，反转列表节点中的指针，以便它们指向上一个节点而不是下一个节点。记住最后一个节点。
3. 现在，您有了指向第一个节点和最后一个节点的指针，并且可以从任一端向中间迭代，直到找到差异（无回文）或到达中间（回文）为止。
4. 倒转下半部分的指针，使它们恢复到原始状态。

这将仅需要恒定的额外空间，并且具有线性执行时间。