essay
hot100-回文链表
#算法
hot100——回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
解法
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
// Step 1: 快慢指针找中点
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// 此时 slow 指向：
// - 奇数长度：中间节点（如 1→2→3→2→1 → slow=3）
// - 偶数长度：前半部分最后一个（如 1→2→2→1 → slow=第一个2）
// Step 2: 反转后半部分（从 slow.Next 开始）
var prev *ListNode
curr := slow.Next
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
// prev 现在是反转后的新头（即原链表尾）
// Step 3: 比较前半部分和反转后的后半部分
p1 := head // 从前向后
p2 := prev // 从后向前（因已反转）
for p2 != nil { // 后半部分长度 ≤ 前半部分，只需遍历 p2
if p1.Val != p2.Val {
return false
}
p1 = p1.Next
p2 = p2.Next
}
return true
}