给定一个链表的头节点head，请判断该链表是否为回 文结构。
例如: 1->2->1，返回true。
1->2->2->1，返回true。
15->6->15，返回true。
1->2->3，返回false。
进阶：
如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。
代码实现：
//快慢指针，都是从头开始
public class IsPalindromeList {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
pre.next = prepre;
prepre = pre;
}
if(fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
}
class ListNode {
int val;
// 下一个链表对象
ListNode next;
//赋值链表的值
ListNode(int x) { val = x; }
}
代码实现2：
//快慢指针，反转前半部分链表，时间O(n),空间O(1)
public class IsPalindromeList {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
ListNode slow = head, fast = head.next, pre = null, prepre = null;
while(fast != null && fast.next != null) {
//反转前半段链表
pre = slow;
slow = slow.next;
fast = fast.next.next;
//先移动指针再来反转
pre.next = prepre;
prepre = pre;
}
ListNode p2 = slow.next;
slow.next = pre;
ListNode p1 = fast == null? slow.next : slow;
while(p1 != null) {
if(p1.val != p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
}
}
class ListNode {
int val;
// 下一个链表对象
ListNode next;
//赋值链表的值
ListNode(int x) { val = x; }
}
原文：https://www.cnblogs.com/cdlyy/p/12081579.html