题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
如果一个链表从前往后读和从后往前读都一样，那么它就是回文链表。
示例分析
示例 1
输入: head = [1,2,2,1]
输出: true
因为从前往后读是：
1,2,2,1
从后往前读也是：
1,2,2,1
所以它是回文链表。
示例 2
输入: head = [1,2]
输出: false
从前往后读是：
1,2
从后往前读是：
2,1
两者不一样，所以不是回文链表。
解题思路
这道题最直接的一种做法，就是先把链表中的所有节点值取出来，存进一个数组（或者 List）中。
这样问题就从：
判断链表是否是回文
转化成了：
判断一个数组是否是回文
而判断数组是否是回文就很简单了，只需要使用双指针：
-
一个指针从左往右走
-
一个指针从右往左走
-
依次比较对应位置的值是否相等
如果所有位置都相等，那么就是回文；只要有一对不相等，就不是回文。
你给出的代码正是这个思路。
为什么这道题可以先转成数组
链表本身的特点是：
-
只能从前往后访问
-
不能像数组那样通过下标随机访问
而“回文”这个问题，本质上需要我们同时比较：
-
第 1 个元素和最后 1 个元素
-
第 2 个元素和倒数第 2 个元素
-
第 3 个元素和倒数第 3 个元素
对于数组来说，这非常容易。 但对于单链表来说，如果每次都想找到“倒数第几个节点”，会很麻烦。
所以先把链表值存进数组，等于是把问题转化成了更容易处理的形式。
这是一种非常常见的思路：
如果链表本身不方便操作，就先提取值，转化成更容易处理的数据结构。
代码实现
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}
代码解析
1. 用列表保存链表中的所有值
List<Integer> vals = new ArrayList<Integer>();
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
这段代码做的事情很简单：
-
从链表头开始遍历
-
每访问到一个节点，就把它的值加入列表
vals -
遍历结束后，
vals中就保存了链表的完整顺序
比如链表：
1 -> 2 -> 2 -> 1
遍历结束后：
vals = [1, 2, 2, 1]
这样后面就可以像操作数组一样去判断它是不是回文。
2. 定义头尾双指针
int front = 0;
int back = vals.size() - 1;
-
front指向数组最左边 -
back指向数组最右边
接下来不断比较它们对应的值。
3. 从两端向中间比较
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
如果左边和右边的值不同，就说明不是回文，直接返回 false。
如果相同，就继续向中间收缩。
为什么循环条件是：
front < back
因为当两个指针相遇或者交错时，说明整个数组已经比较完了。
4. 全部比较完成后返回 true
return true;
说明所有对应位置的值都相等，因此链表是回文链表。
示例推演
我们以这个链表为例：
1 -> 2 -> 2 -> 1
第一步：提取链表值
遍历后得到：
vals = [1, 2, 2, 1]
第二步：双指针比较
初始状态：
front = 0
back = 3
比较：
vals[0] = 1
vals[3] = 1
相等，继续。
然后：
front = 1
back = 2
比较：
vals[1] = 2
vals[2] = 2
相等，继续。
接着：
front = 2
back = 1
此时 front < back 不成立，循环结束。
说明整个数组是回文，所以返回 true。
再看一个不是回文的例子
链表：
1 -> 2
提取后：
vals = [1, 2]
双指针比较：
-
front = 0 -
back = 1
比较得到：
vals[0] = 1
vals[1] = 2
不相等，所以直接返回 false。
为什么这里要用 equals 而不是 ==
代码里写的是：
if (!vals.get(front).equals(vals.get(back))) {
这里使用 equals 是因为 vals 中存的是 Integer 对象，而不是基本类型 int。
在 Java 中，比较两个对象的值是否相等，应该优先使用 equals。
如果用 ==，比较的是对象引用地址，不够稳妥。
所以这里写 equals 是更规范、更安全的做法。
这种做法的优点
这份代码的优点非常明显：
1. 思路直观
先遍历链表存值，再判断数组是否回文，非常容易理解。
2. 写法简单
代码量不大，逻辑清晰，适合这道题的入门思路。
3. 不会破坏原链表结构
有些进阶做法会去反转链表后半部分，而这种做法只是读取链表值，不会修改原链表。
这种做法的缺点
缺点也很明确：
需要额外的
O(n)空间。
因为我们开了一个 List<Integer> 来保存所有节点值。
如果题目进一步要求：
-
时间复杂度
O(n) -
空间复杂度
O(1)
那么这种方法就不够优了。
那时通常要用：
-
快慢指针找中点
-
反转后半部分链表
-
再比较前后两段
但从易理解和易实现的角度来说，你这份代码已经是非常好的基础解法。
复杂度分析
设链表长度为 n。
时间复杂度
O(n)
-
第一次遍历链表，把值加入数组，需要
O(n) -
第二次用双指针比较数组，需要
O(n)
所以总时间复杂度仍然是 O(n)。
空间复杂度
O(n)
因为额外使用了一个列表来保存链表中的所有值。
和进阶做法对比
当前这种“数组 + 双指针”做法
优点：
-
思路最直观
-
代码简单
-
不会修改链表结构
缺点：
-
需要
O(n)额外空间
进阶做法：快慢指针 + 反转后半链表
优点：
-
空间复杂度可以做到
O(1)
缺点：
-
实现更复杂
-
需要处理链表反转和还原的问题
-
更容易写错
所以如果只是先把题做出来，当前这份代码已经很合适。 如果是面试追求更优空间复杂度，再去掌握进阶做法会更好。
总结
这道题的核心思路其实很简单：
-
先遍历链表，把所有节点值保存到数组中
-
再用双指针从两端向中间比较
-
只要有一对值不相等，就不是回文
-
如果全部相等，就是回文链表
你可以把这题总结成一句话：
先把链表转成数组，再把链表回文问题转化成数组回文问题。
