题目传送门：回文链表
请判断一个链表是否为回文链表。
示例1：
输入: 1->2
输出: false
示例2：
输入: 1->2->2->1
输出: true
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
方法一：将链表的值复制到数组中然后使用双指针法
该方法使用了数组的特性，因为数组查找起来非常简单，而链表只能从前到后查找。首先我们将链表的值复制到数组中，然后使用头尾两个指针，两个指针都往数组中间遍历，如果值都相等的话则链表为回文链表。
- 时间复杂度：O(n)，其中 n 指的是链表的元素个数。
- 第一步：遍历链表并将值复制到数组中，O(n)
- 第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)
- 总的时间复杂度：O(2n) = O(n)
- 空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
//1.新建ArrayList
List<Integer> vals = new ArrayList<>();
//把LinkedList的值赋给ArratList
while(head != null) {
vals.add(head.val);
head = head.next;
}
//分别创建头尾两个指针，然后比较两个指针节点的值
//要注意这里为包装类，不能使用!=来进行比较，需要使用! .equals()来做判断
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;
}
}
方法二：切成两半，把后半段反转，然后比较两半是否相等。
因为本题的进阶要求为使用 O(1) 的空间复杂度，所以我们不能使用额外的空间，那么，改怎么去解决这个问题呢？
避免使用 O(n) 额外空间的方法就是改变输入。
我们可以将链表的后半部分反转（修改链表结构），然后比较两半是否相等。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// 在这个算法中，如果链表为奇数个节点，那么最后比较中经过反转后的链表要比前半段多一个最中间的节点
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if(fast != null) slow = slow.next; // 如果链表为偶数，则将slow移动到中间位置的下一个节点
cut(head, slow); // 分割链表
return isEqual(head, reverse(slow)); // 反转链表的后半段并返回结果
}
// 切断链表方法
private void cut(ListNode head, ListNode cutNode) {
while(head.next != cutNode) {
head = head.next;
}
head.next = null;
}
// 反转链表方法
private ListNode reverse(ListNode head) {
ListNode newNode = null;
while(head != null) {
ListNode nextNode = head.next;
head.next = newNode;
newNode = head;
head = nextNode;
}
return newNode;
}
// 比较两个链表的值是否相等的方法
private boolean isEqual(ListNode l1, ListNode l2) {
while(l1 != null && l2 != null) {
if(l1.val != l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true;
}
}
自己遇到的坑：我在用第二种方法做这个题的时候遇到了一个很大的坑，找了好久，最终还是写了测试程序 debug 之后，才意识到自己的问题。在第一次写第二种方法的时候 cut 方法中的 while 循环中的判断条件我写的是 head != cutNode ，发现测试算法最后提交时是错误的，通过不了，改成 head.next != cutNode 之后就成功了。没办法，自己空想想不出来，就只好去 debug 一步步看程序的运行结果，在好几遍的 debug 之后，我终于发现了错误原因。因为算法的 cut 方法的目标为切断链表，把链表一分为二后再来对后半段进行翻转和比较的操作。我们的目标为把从链表头部到 slow 指针前面的一个节点和从 slow 到尾节点切开。所以当 head != slow 的话，每次 slow 都会被切断（切的位置在 slow 后面），保留 slow 节点的这个值，所以算法出错。
举个例子：如果测试用例为 [1,0,1]，是一个回文链表。如果 cut 方法中 while 的判断条件为 head != slow 的话，经过上面的指针移动 slow 会移动到链表中 0 这个节点。因为判断条件会使 head 移动到 slow 指针这个位置，所以下一步 head.next = null 的时候链表会在 0 这个节点后面切一刀。但是这一刀会影响 slow 这个将要被拿去翻转的链表，也就是 slow 这个链表也会被切断，变为只有一个 0 节点，之后的比较中就会出错。
但是判断条件如果为 head.next != cutNode 的话，切点就在 slow 指针前面，slow 这个后半段链表就不会受影响，而且当链表为奇数个节点时 slow 链表也会多出一个中间结点，但这并不影响后面的比较，所以这样写才是正确的。