234-回文链表

来源：力扣（LeetCode）

链接：234. 回文链表

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

请判断一个链表是否为回文链表。

示例 1：

1. 输入：1->2
2. 输出：false

示例 2：

1. 输入：1->2->2->1
2. 输出：true

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

二、题解

2.1 暴力法

算法：

1. 遍历链表并复制一份
2. 同时把复制出来的链表反转
3. 使用2个指针分别遍历两个链表对比每个节点

算法复杂度：

• 时间复杂度：O(n)，需要遍历两次链表。
• 空间复杂度：O(n)，需要拷贝一份链表。

2.2 快慢指针

判断是否回文数核心思想是先找到链表的中间节点，然后从中间节点开始往两边对比、或者从两边往中间节点对比，以此判断是否为回文数。

算法：

使用2个指针，快指针每次走一步，慢指针每次走两步。当快指针到链表末尾的时候，慢指针在链表中间。这个时候反转后半部分链表，再使用两个指针从链表两端朝中间遍历即可判断出是不是回文。

图示：

当快指针走到末尾的时候，慢指针刚好走到一半，中间节点就在p1和p1前一个节点之间：

以下是节点个数为奇数时，快慢指针从开始到结束时候的状态，中间节点是p1的前一个节点：

可以看到不管链表个数是奇数还是偶数，中间节点都是在慢指针p1附近。

优化：

上面的快慢指针算法的执行步骤：

1. 快指针遍历到末尾（遍历了一半的链表）。
2. 反转慢指针到快指针这一段（遍历了一半的链表）。
3. 从两端往中间遍历（遍历了一半的链表）。

整个时间复杂度是O(n)，虽然是O(n)，但是实际上链表遍历了1.5次。因为要对比整个链表，所以算法的时间复杂度不可能低于O(n)，O(n)最理想的情况就是只遍历一次，因此可以想办法优化掉多余的0.5次遍历。

算法如下：

1. 快慢指针分别遍历链表，遍历的过程中，把慢指针经过的节点反转。
2. 当快指针走到链表末尾的时候，慢指针依旧在链表中间的位置，但是此时，慢指针前面的节点都已经反转了。
3. 分别从满指针前后朝两端遍历，对比每个节点。

该算法把前面的步骤1和2合并成了一个操作，减少了一次遍历操作（需要遍历一半链表节点），最后只要遍历1次链表即可完成判断链表是否回文。算法要注意区分奇数个节点和偶数个节点。

当链表节点个数是偶数个的时候，快指针在指向NULL时，p1前面的就是链表的前半段，从p1开始就是后半段：

链表节点个数是奇数个的时候，p2不会走到NULL（p2要走2步，没有更多的节点了），此时p1在最中间的节点。p1之前是链表的前半段，p1之后就是链表的后半段：

代码：

这里要注意的是pre指针的作用，从上面的图示中可以发现，不管是奇数还是偶数个节点，反转后都是从slow节点前分隔开的。因此pre的作用就是保存slow前面的节点，用于后续回文数比对。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)