一、题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

二、解决方法

方法一：快慢指针+反转链表

核心思想：

创建两个指针，快指针一次走两步，慢指针一次走一步 ，当快指针走到终点时，此时慢指针刚好位于中心位置。之后从中心位置开始，反转后半部分指针，比较前半部分指针和反转后的后半部分指针，若每个结点的值相同，则为回文

代码:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def isPailndrome(self,head:ListNode)->bool:
        if not head or not head.next:
            return True

        # 1. 快慢指针找到中点
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 反转后半部分链表
        prev = None
        curr = slow
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        # prev 为反转后的链表头

        # 3. 比较前半部分和后半部分
        left, right = head, prev
        while right:  # 注意：后半部分可能更短
            if left.val != right.val:
                return False
            left = left.next
            right = right.next

        return True

方法二:利用列表辅助

核心思想：

把链表中的数值，全部添加到数组中，之后使用切片反转，直接判断两个列表是否相等

代码：

def isPalindrome(head):
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    return vals == vals[::-1]