回文链表

怎样从“判断链表 1→2→2→1 是否回文。数组容易判断，链表难点在于只能通过 next 向后遍历。”推导出 链表 · 找中点+反转，并证明每次状态变化都不会漏掉答案？

中心结论：快慢指针找到左半结束点，从 firstHalfEnd.Next 反转后半，p1/p2 只沿 next 比较，最后可选恢复链表。

判断一个链表是否是回文链表。要求时间复杂度 O(n)，空间复杂度 O(1)。

在本站主例中，判断链表 1→2→2→1 是否回文。数组容易判断，链表难点在于只能通过 next 向后遍历。

算法最终需要得到或观察：右半段 2→1 反转成 1→2，与左半 1→2 逐位相等，返回 true。

复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 slow/fast、firstHalfEnd、prev/cur/next、p1/p2、result。
3. 3转移每一步按照 快慢指针找到左半结束点，从 firstHalfEnd.Next 反转后半，p1/p2 只沿 next 比较，最后可选恢复链表。
4. 4收尾读取 右半段 2→1 反转成 1→2，与左半 1→2 逐位相等，返回 true。，并复核边界与复杂度。

画清每根 next 指针改变前后的归属，再写代码。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：slow/fast、firstHalfEnd、prev/cur/next、p1/p2、result。

这道题只需要在第 143 题上面改改就可以了。思路是完全一致的。先找到中间结点，然后反转中间结点后面到结尾的所有结点。最后一一判断头结点开始的结点和中间结点往后开始的结点是否相等。如果一直相等，就是回文链表，如果有不相等的，直接返回不是回文链表。

快慢指针找到左半结束点，从 firstHalfEnd.Next 反转后半，p1/p2 只沿 next 比较，最后可选恢复链表。

执行过程中持续维护：slow/fast、firstHalfEnd、prev/cur/next、p1/p2、result。

正确性依赖以下不变量：右半段长度为 floor(n/2)，循环只比较到 p2 == nil。；奇数长度的中间节点自己对称，不参与比较。

面试时可以压缩为：单链表不能从尾往前走，所以用 slow/fast 找左半结束点，反转后半段后让 p1/p2 都沿 next 前进比较；比较完可再反转恢复链表，时间 O(n)，额外空间 O(1)。

落到当前题，执行机制可以压缩为：快慢指针找到左半结束点，从 firstHalfEnd.Next 反转后半，p1/p2 只沿 next 比较，最后可选恢复链表。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入判断链表 1→2→2→1 是否回文。数组容易判断，链表难点在于只能通过 next 向后遍历。 因为：快慢指针找到左半结束点，从 firstHalfEnd.Next 反转后半，p1/p2 只沿 next 比较，最后可选恢复链表。
2. 2找中点 + 反转后半fast 到末尾时 slow 在中点。 因为：O(n) 找中点。
3. 3中点候选 slow=1继续找中点。 因为：fast 走两倍速度。
4. 4中点候选 slow=2继续找中点。 因为：fast 走两倍速度。
5. 5values[0] == values[3]比较对称结点。 因为：继续向内。
6. 6values[1] == values[2]比较对称结点。 因为：继续向内。
7. 7是回文比较结束。 因为：O(n) 时间,O(1) 额外空间。
8. 8收尾与复杂度右半段 2→1 反转成 1→2，与左半 1→2 逐位相等，返回 true。 因为：时间 O(n) · 空间 O(1)。快慢指针找到左半结束点，从 firstHalfEnd.Next 反转后半，p1/p2 只沿 next 比较，最后可选恢复链表。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 解法一
func isPalindrome(head *ListNode) bool {
	slice := []int{}
	for head != nil {
		slice = append(slice, head.Val)
		head = head.Next
	}
	for i, j := 0, len(slice)-1; i < j; {
		if slice[i] != slice[j] {
			return false
		}
		i++
		j--
	}
	return true
}

// 解法二
// 此题和 143 题 Reorder List 思路基本一致
func isPalindrome1(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	res := true
	// 寻找中间结点
	p1 := head
	p2 := head
	for p2.Next != nil && p2.Next.Next != nil {
		p1 = p1.Next
		p2 = p2.Next.Next
	}
	// 反转链表后半部分  1->2->3->4->5->6 to 1->2->3->6->5->4
	preMiddle := p1
	preCurrent := p1.Next
	for preCurrent.Next != nil {
		current := preCurrent.Next
		preCurrent.Next = current.Next
		current.Next = preMiddle.Next
		preMiddle.Next = current
	}
	// 扫描表，判断是否是回文
	p1 = head
	p2 = preMiddle.Next
	// fmt.Printf("p1 = %v p2 = %v preMiddle = %v head = %v\n", p1.Val, p2.Val, preMiddle.Val, L2ss(head))
	for p1 != preMiddle {
		// fmt.Printf("*****p1 = %v p2 = %v preMiddle = %v head = %v\n", p1, p2, preMiddle, L2ss(head))
		if p1.Val == p2.Val {
			p1 = p1.Next
			p2 = p2.Next
			// fmt.Printf("-------p1 = %v p2 = %v preMiddle = %v head = %v\n", p1, p2, preMiddle, L2ss(head))
		} else {
			res = false
			break
		}
	}
	if p1 == preMiddle {
		if p2 != nil && p1.Val != p2.Val {
			return false
		}
	}
	return res
}

// L2ss define
func L2ss(head *ListNode) []int {
	res := []int{}
	for head != nil {
		res = append(res, head.Val)
		head = head.Next
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="palindrome", values=[1,2,2,1]
    //    期望：右半段 2→1 反转成 1→2，与左半 1→2 逐位相等，返回 true。
    //
    // 2. 失败 / 未命中
    //    检查：把节点值塞数组后说是 O(1) 空间。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC125 验证回文串；LC876 中间结点
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意判断链表 1→2→2→1 是否回文。数组容易判断，链表难点在于只能通过 next 向后遍历。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化快慢指针找到左半结束点，从 firstHalfEnd.Next 反转后半，p1/p2 只沿 next 比较，最后可选恢复链表。
4. 4证明右半段长度为 floor(n/2)，循环只比较到 p2 == nil。；奇数长度的中间节点自己对称，不参与比较。
5. 5复杂度时间 O(n)，空间 O(1)