image.png
链表的定义：
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
链表的构建：
vals = [1, 2, 3, 3, 2, 1]
# vals = [1, 2, 3, 4, 3, 2, 1]
num = len(vals)
root = ListNode(vals[0])
p = root
for i in range(1, num):
p.next = ListNode(vals[i])
p = p.next
构建出来的链表为：1->2->3->3->2->1或者1->2->3->4->3->2->1，都是属于回文链表。
最简单的方法，将链表的元素存入列表，然后通过索引判断是否为回文链表，时间复杂度为O(n), 空间复杂度为O(n)
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head: return True
res = []
while head:
res.append(head.val)
head = head.next
num = len(res)
for i in range(num//2):
if res[i] != res[-(i+1)]:
return False
return True
题目中进阶要求空间复杂度为O(1), 可以使用原地反一部分转链表再比较的方法。
整个流程可以分为以下五个步骤：
（1）找到前半部分链表的尾节点（可以统计链表的长度，然后再遍历得到中间节点。更快的方法是用快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到链表的结尾时，慢指针走到中间节点）。
（2）反转后半部分链表。
（3）判断是否回文。
（4）恢复链表（题目不要求，但是最好还原）。
返回结果。
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if head is None:
return True
# 找到前半部分链表的尾节点并反转后半部分链表
# 如果是奇数个，找到的是最中间的节点
first_half_end = self.end_of_first_half(head)
second_half_start = self.reverse_list(first_half_end.next)
# 判断是否回文
result = True
first_position = head
second_position = second_half_start
while result and second_position is not None:
if first_position.val != second_position.val:
result = False
first_position = first_position.next
second_position = second_position.next
# 还原链表并返回结果
first_half_end.next = self.reverse_list(second_half_start)
return result
def end_of_first_half(self, head):
fast = head
slow = head
while fast.next is not None and fast.next.next is not None:
fast = fast.next.next
slow = slow.next
print(slow.val)
print(fast.val)
return slow
def reverse_list(self, head):
previous = None
current = head
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous
测试代码：
res_str = test_object.isPalindrome(root)
print(res_str)
部分代码来自：
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
