当前位置 博文首页 > "大梦三千秋的博客：LeetCode 234. 回文链表 | Python
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/palindrome-linked-list/
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解决这道题，其实跟前面 143. 重排链表 的思想有点类似，以下是前阵子写的关于 143 题的解题思路，有兴趣的话可以进行阅读，多多支持。
143. 重排链表 | 线性表、切分链表（迭代+双指针）
一般情况下，我们要求数组是否是回文，可以使用双指针的话方法。初始定义双指针分别指向数组的头尾元素，指针往中间移动进行判断。
但是链表不能够随意访问特定的数据，上面的方法也就无效。那么，这里可以使用列表，遍历链表存储元素的值，然后再使用上面的方法进行判断。
具体的代码实现如下。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 声明列表存储链表元素的值
lst = []
node = head
while node:
lst.append(node.val)
node = node.next
# 定义双指针，
start = 0
end = len(lst) - 1
# 遍历列表，判断是否是回文
while start < end:
if lst[start] != lst[end]:
return False
start += 1
end -= 1
return True
时间复杂度： O ( N ) O(N) O(N)， N N N 表示链表的元素个数。列表存储链表元素值与判断是否是回文，均为线性时间，所以最终时间复杂度为 O ( N ) O(N) O(N)。
空间复杂度： O ( N ) O(N) O(N)， N N N 表示链表的元素个数。列表存储链表元素的开销。
进阶部分内容，要求实现空间复杂度 O ( 1 ) O(1) O(1) 的算法，而前面的方法使用了列表额外存储。
不过根据前面的方法，定义双指针分别指向首尾往中间移动进行判断。对于链表而言，我们可以考虑找到链表的中间节点，将链表切分为前后两部分，然后将后面部分翻转，然后与前面部分进行比对。例如：
输入: 1->2->2->1
找到中间节点进行切分，
前面部分 1->2
后面部分 2->1
翻转后面部分，进行比对
前面部分 1->2
后面部分 1->2
具体的做法：
上面的做法中，破坏了链表的结构。建议将其进行恢复。
具体的代码实现如下。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
def search_middle_node(head):
"""查找链表中间节点
"""
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverse_list(head):
"""翻转链表
"""
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
if not head:
return True
# 找中间节点，切分链表
mid = search_middle_node(head)
latter_part = mid.next
# 翻转后面部分
reversed_latter_part = reverse_list(latter_part)
# 因为翻转链表会破坏链表结构，得到结论先不返回，恢复链表后再返回
res = True
# 定义指针分别指向前后两部分链表的头部
p = head
q = reversed_latter_part
# 开始遍历，比对
while res and q:
# 如果对应的节点值不同，那么不是回文
if p.val != q.val:
res = False
p = p.next
q = q.next
# 还原链表
mid.next = reverse_list(reversed_latter_part)
# print(head)
return res
公众号 【书所集录】
如有错误，烦请指正，欢迎指点交流。
cs