234. 回文链表

题目

234. 回文链表（简单）

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

示例 1：

输入：

[1,2,2,1]

输出：

true

示例 2：

输入：

[1,2]

输出：

false

提示：

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

思路

方法一数组复制：把链表值按顺序存进数组，判断数组是否与其逆序相同，空间 $O(n)$。

方法二递归双指针：利用递归天然的后序性质——fun(bck) 递归到链尾后回溯时相当于从尾往头走，与外层从前往后走的 prev 逐一比较；不一致即返回 False。进阶标准解法是「找中点 + 反转后半 + 比较」，可做到 $O(1)$ 空间。

代码

方法一：数组复制

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        vals = []
        curr = head
        while curr is not None:
            vals.append(curr.val)
            curr = curr.next
        return vals == vals[::-1]

方法二：递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        prev = head
        def fun(bck):
            nonlocal prev
            if bck is not None:
                if not fun(bck.next):
                    return False
                if prev.val != bck.val:
                    return False
                prev = prev.next
            return True
        return fun(head)