python - 具有 O(1) 额外空间的 Python 回文链表

Question

这是#234 Leetcode 问题:

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

这个问题很容易用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

这适用于小样本，但给出了

maximum recursion depth exceeded

谁能提供仅使用 O(1) 空间的解决方案？谢谢。

Answer 1

如果允许您就地修改列表，您可以执行以下操作:

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

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