将链表的前半部分反转。 然后从中间开始向两边逐节点比较。 利用三个指针,详见注释。
python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
prev = None
slow = fast = head
while fast and fast.next:
fast = fast.next.next # 快指针每次走两步
slow.next,prev,slow = prev,slow,slow.next # 慢指针指向的节点每次去更改后继节点,然后慢指针每次走1步
# 节点数为偶数时,prev指向中间靠左的第一个节点,slow指向中间靠右的第一个节点,fast指向None
# 节点数为奇数时,prev指向中间靠左的第一个节点,slow指向最中间的节点,fast指向最右边
if fast: # 说明节点数为奇数
slow = slow.next
# 从中间到两边开始对比。如果是回文链表,则最后prev和slow都是None
while prev and slow and prev.val==slow.val:
prev = prev.next
slow = slow.next
return not prev