Python 中的回文链表，带有 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. 在下半场反转指针，使它们恢复到原始状态。

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

Answer 2

我评论了解决方案的关键点：

class Solution:
    def with_array(self,head:ListNode)->bool:
        # this makes S:O(N)
        nums=[]
        while head:
            nums.append(head.val)
            head=head.next
        l,r=0,len(nums)-1
        while l<=r:
            if nums[l]!=nums[r]:
                return False
            l+=1
            r-=1
        return True
    def optimum(self,head:ListNode)->bool:
        fast_pointer=head
        slow_pointer=head
        # I wanna reach the end of the linked list. I stop when fast_pointer.next=None
        while fast_pointer and fast_pointer.next:
            # we are forwarding fast_pointer twice
            fast_pointer=fast_pointer.next.next
            # while slow reach middle, fast will reach to the end
            slow_pointer=slow_pointer.next
            # at the end of this while loop, slow_pointer will be in middle, fast_pointer will be at the end
        
        # reverse the second half of the list, from slow_pointer till the fast_pointer
        # at the end of the reverse, prev will point to the last node 
        prev=None
        while slow_pointer:
            temp=slow_pointer.next
            slow_pointer.next=prev
            # eventually prev will point to the last node
            prev=slow_pointer
            slow_pointer=temp
        # check if it is a palindrome
        # remember, after reversing, prev=tail
        left,right=head,prev
        while right:
            if left.val!=right.val:
                return False
            left=left.next
            right=right.next
        return True