1. 题目描述
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
2. 解题思路
由于只能用 O(1) 的空间复杂度，那么不能用数组，只能采用 指针法。（通常情况下指针法的空间复杂度是最低的，即 O(1)。当题目要求空间复杂度为 O(1) 的时候也要联想起 指针法）
2.1 寻找链表中间节点
可以采用快慢指针，slow 指针每步走 1 个节点，fast 指针每步走 2 个节点。那么当 fast 走到尾节点的时候，slow 一定刚好走到中间节点。（根据节点数是奇数或者偶数有一个节点的误差，但是不是重点，后面可以补偿上）。
没错，又是追及问题的思维。之前在讲到链表的题目时还有类似的题目。详见以下链接：
【LeetCode】141 环形链表 I，142. 环形链表 II（双指针 中学追及问题）
【LeetCode 】160. 相交链表（双指针法 Python 7行代码 中学追及问题）
2.2 反转前半部分链表
可以再使用 2 个指针，pre 和 prepre，紧跟在 slow 的后面一个节点，进行链表的反转
2.3 中心扩展对比
从中心开始，向两边扩展，两边的节点一一比对，都相同的话就是回文链表，只要有一对节点不相同的话就不是回文链表
2.4 细节处理
由于节点个数存在奇数和偶数的区别，那么 slow 的处理稍有区别
-
偶数节点个数：slow 指针 刚好指向 中间两个节点 中的后一个节点，那么可以直接进行配对比较
-
奇数节点个数：slow 指针指向正中间的节点，需要先往后挪一个节点再比对
2.5 详细图解
2.5.1 偶数个数节点
slow 指针 刚好指向 中间两个节点 中的后一个节点，那么可以直接进行配对比较
2.5.2 奇数个数节点
和偶数节点个数的时候唯一的区别是：slow 指针指向正中间的节点，需要先往后挪一个节点再比对 （具体可对照后面的代码查看）
3. Python 代码
# 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:
if (head is None) or (head.next is None):
return True
slow = head
fast = head
pre = head
prepre = ListNode(None)
while(fast and fast.next):
pre = slow # pre 紧跟在slow 后面一步
slow = slow.next # 快慢指针用于找到中间节点
fast = fast.next.next
pre.next = prepre # 用于反转前半部分链表
prepre = pre
if (fast): # 如果跳出上一个while循环是 fast.next is None,那么就是奇数个节点，slow需要再走一步
slow = slow.next
while(pre and slow): # 从中间对称的位置往两边扩展，比对两边的数是否相等
if (pre.val != slow.val):
return False
pre = pre.next
slow = slow.next
return True
京公网安备 11010502036488号