Python 中具有 O(1) 额外 Space 的回文链表

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) space 解决。但是，我无法找出 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) space 的解决方案？谢谢。

Answer 1

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

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

这将只需要常量附加 space，并且具有线性执行时间。

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

Python 中具有 O(1) 额外 Space 的回文链表

Palindrome Linked List in Python with O(1) Extra Space

python

algorithm

linked-list

palindrome