如何在保持原始链接列表不变的情况下反转链接列表

Question

如何反转保持原始的链表？如果我反转链接列表，它也会更改原始列表。

class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
p = head
q = self.reverse_list(head)


while p and q:     
if p.val != q.val:
return False
else:
p = p.next
q= q.next
return True


def reverse_list(self, head):
curr = head
prev = None
while curr is not None:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp

return prev

Answer 1

您可以使用递归来制作一个非常美观的(但在python中不是超高效的(解决方案。基本上，你可以切换递归的顺序，给你一个正向生成器和一个反向生成器，然后压缩和比较

class Solution:
def isPalindrome(self, head):
return all(a.val == b.val 
for a,b 
in zip(self.forward(head), self.backward(head)))

def forward(self, head):
if head is None:
return
yield head
yield from self.forward(head.next)

def backward(self, head):
if head is None:
return 
yield from self.backward(head.next)
yield head

这很有吸引力，但由于递归限制，不太可能用于非常大的列表。

对于较大的输入，你可以制作一个forward()生成器的非递归版本，并从中呈现一个列表

class Solution:
def isPalindrome(self, head):
v = list(self.forward(head))
return v == v[::-1]

def forward(self, head):
while head:
yield head.val
head = head.next

这使用了O(n(空间，但应该表现得相当好。

另一种解决方案是在列表中迭代，并在执行过程中添加parent属性。最后，您将获得列表的尾部，并且可以跟随父引用，同时再次从头开始运行列表并进行比较。