当前位置 博文首页 > hdtopku：leetcode 234. Palindrome Linked List-回文链表|双指
【思路】
题目要求时间复杂度为 O(n)，空间复杂度为O(1)，那么蛮力算法首先排除了。
链表长度分为奇数和偶数情况。如图所示，我们先以偶数长度进行讨论。我们要达到的目的是一次遍历过后，将链表分为前半部分和后半部分，并且对前半部分进行了反转。
head 的作用是指向前半部分的头结点，
mid 的作用是指向后半部分的头结点，
pre 的移位时用作缓存，
tail 如果为奇数个节点时指向最后一个节点，如果偶数个节点时指向倒数第二个节点。
进而判断 mid 和 head 中的每个节点是否都相等，如果相等就返回 true，否则，返回 false。
如果是奇数的情况，那么就要将 head 前移移位，循环过后结果如上图所示：
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode mid = head.next, tail = head, pre = head;
while (tail.next != null && tail.next.next != null) {
tail = tail.next.next; //①
head = mid; //②
mid = mid.next; //③
head.next = pre; //④
pre = head; //⑤
}
if (tail.next == null) head = head.next;
while (mid != null) {
if (head.val != mid.val) return false;
mid = mid.next;
head = head.next;
}
return true;
}