请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
起初遍历链表，获取链表的顺序字符串str，然后调用reverse方法，从而获取字符串的逆序reverseString，返回值为str.equals(reverseString)即可.虽然如此，但是最后提交代码的时候会发现超时了。
所以为了避免超时，我们将整条链表分成两条链表，其中一条链表利用双指针实现链表的逆序，然后同时遍历这两条子链表，判断节点的值是否相同，如果不相同，说明这条链表不是一个回文链表，否则当链表遍历完时，此时直接返回true即可。
对应的代码:
class Solution {
/*
前后双指针实现链表的逆序.
首先对其中的链表划分成为一半，然后对这一半链表实现逆序
*/
public boolean isPalindrome(ListNode head) {
//获取链表的终点
ListNode pre,cur,newHead;
pre = head;
cur = head;
/*
通过这个操作，pre是整条链表的前一般链表的最后一个节点
注意while循环的判断条件必须是这样的，如果不这样写的
话，那么就会由于链表的节点个数的奇偶性，从而导致pre
节点的错误。这个是可以通过例子来证明的。
例如如果while循环条件改成了cur != null && cur.next != null
，那么链表如果是[1,2,2,1]，那么就导致了pre在第2个2这个节点的位置
所以while循环的循环条件是cur != null && cur.next != null &&
cur.next.next != null.
*/
while(cur != null && cur.next != null && cur.next.next != null){
pre = pre.next;
cur = cur.next.next;
}
newHead = pre.next;
pre.next = null;
newHead = reverse(newHead); //对链表的后半部分进行逆序操作
while(newHead != null && head != null){
/*
遍历两部分的链表，判断他们的值是否相同，如果不同，说明不是回文链
表，直接返回false，否则继续遍历，直到遍历完newHead为止
之所以说是后一部分链表完为止时直接返回true，是因为如果链表的个数时
奇数的时候，那么pre刚好在链表的中点的位置，此时前一部分链表比后一
部分的链表刚好多了一个节点，而这个节点刚好在链表的中点位置，所以
在退出循环之后，就可以直接返回true并没有错误
*/
if(newHead.val != head.val)
return false;
newHead = newHead.next;
head = head.next;
}
return true;
}
public ListNode reverse(ListNode head){
ListNode pre = null,cur = head,tmp;
while(cur != null){
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
运行结果:
但是代码依旧可以再次优化，通过观察代码，我们发现可以在找到链表的中点的同时，对前一部分的链表进行逆序操作，这样的话就可以直接遍历前一部分和后一部分的链表来判断即可。优化后的代码为:
class Solution {
/*
在获取链表的中点的同时，对慢指针实现链表的逆序
*/
public boolean isPalindrome(ListNode head) {
ListNode pre,cur,newHead = null,tmp;
pre = head;
cur = head;
/*
这里和上面的while循环判断条件不同，是因为这个代码不单单时找到
链表的中点，同时实现前半部分的链表逆序。
所以考虑到如果链表的节点的个数的奇偶性的不同，如果while循环的
判断条件依旧时cur != null && cur.next != null && cur.next.next
!= null的话，那么对应的代码应该是:
if(cur != null && cur.next == null){
//链表的个数时奇数的时候
pre = pre.next;
}else{
//链表个数为偶数的时候
cur = pre.next;
pre.next = newHead;
newHead = pre;
pre = cur;
}
而如果while循环的判断条件是cur != null && cur.next != null的时
候，添加的操作为
if(cur.next != null)
pre = pre.next;
*/
while(cur != null && cur.next != null){
cur = cur.next.next;
tmp = pre.next;
pre.next = newHead;
newHead = pre;
pre = tmp;
}
if(cur != null) //链表的节点个数是奇数个的时候，pre需要后移才是后一部分链表的头结点
pre = pre.next;
while(pre != null && newHead != null){
if(pre.val != newHead.val)
return false;
pre = pre.next;
newHead = newHead.next;
}
return true;
}
}
运行结果:
