原题
请判断一个链表是否为回文链表。
示例1：
输入： 1->2
输出： false
示例2：
输入： 1->2->2->1
输出： true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解法
思想
双指针解法：
一个快指针一个慢指针，快指针每次移两步，慢指针每次移一步，这样快指针的落点有两种情况：
- 落在最后一个节点上，此时链表节点为奇数个，慢指针落在中间节点上。
- 落在最后一个节点指向的null上，此时链表节点为偶数个，慢指针落在中间靠右第一个节点上。
慢指针将链表分成了两半，将前半部分反转，再与后半部分比较，即可获取结果
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
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;
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode234-%e5%9b%9e%e6%96%87%e9%93%be%e8%a1%a8/
