234. 回文链表

题目链接：234. 回文链表

题目描述

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

核心思考：寻找中点与原地反转

判断一个数组是否是回文很简单，首尾双指针向中间逼近即可。但在单向链表中，由于我们无法从尾部向前逆向遍历，这个问题实际上可以被拆解为三个经典的链表子操作组合：

1. 寻找中点（快慢指针）

前置知识： 这一步的详细推导可以参考我们之前做过的 876. 链表的中间结点

利用快慢指针（fast 和 slow）从头部同步起跑。快指针每次走两步，慢指针每次走一步。当快指针走到链表末尾边界时，慢指针刚好停在链表的中间位置。这一步帮助我们完美地劈开了链表的前半段和后半段。

2. 原地反转后半段链表

这就变成了常见的“反转链表”题型。以慢指针 slow 所指向的中间节点为起点，将链表的后半部分进行原地反转。反转完成后，我们就能拿到一个指向原本链表末端（即反转后首节点）的新头指针。

3. 双指针比对

到了这一步，一切都变得直观了。我们只需将一个指针指向原链表头部 head，另一个指针指向刚刚被反转的后半段头部，然后让它们同时向后游走并行验证节点的值。
由于不论链表整体长度是奇数还是偶数，反转后的后半部分节点数严格等于（甚至少于）前半部分，因此只要以后半段遍历完毕（即遇到空节点 None）作为验证结束的跳出条件，就可以完美规避边界溢出的异常。

解题思路 (Python)

# 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:
        # 找到中间的节点之后反转后半段链表再双指针比对是否是相等即回文
        # 但是回文判断要考虑奇偶数节点的问题，哪个先碰到null？
        if not head or not head.next:
            return True
        # Module 1: 中点定位 (快慢指针)
        # 初始化 slow 和 fast 指针，将 slow 推进到物理中位节点
        slow = head
        fast = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
        # 现在slow的位置就是中心节点
        
        # 原地反转
        # 以 slow 为起点，执行原地反转，返回新后半段的头指针
        # Null -> p1 -> p2 -> p3
        # p1 <- p2 <- p3 <- Null
        prev = None
        curr = slow
        while curr != None:
            temp = curr.next
            curr.next = prev
            prev,curr = curr,temp
        # 现在prev指向的是反转后的首节点

        # 双游标比对
        # 初始化前半段游标 (head) 和后半段游标。
        # 以后半段游标判空为终止条件，进行 val 验证
        p1,p2 = head,prev
        while p2 != None:
            if p1.val == p2.val:
                p1 = p1.next
                p2 = p2.next
            else:
                return False
        return True # 如果所有节点验证通过

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是链表的节点数量。不论是快慢指针找中点、遍历后半部进行原地反转、还是最后的双指针验证比对，每个过程皆为沿着链表单向前进，整体总时间开销依然是严苛的线性级别。
• 空间复杂度：$O(1)$。我们在链表操作全过程中仅变动了部分节点的 next 指向链路，并且只定义了有限几个指针变量记录内存地址，没有开辟任何同数据规模相关的新空间。