题目描述

题目链接234. 回文链表

题解

要求时间复杂度为O(n)，空间复杂度为O(1)。

• 注意回文链表的特点，从中间断开，向两边的节点都一样。
• 所以我们可以利用快慢指针的思想，找到链表中间节点，然后反转前半部分，然后对比两个链表是否相同。
• 找中间节点，和反转前半部分链表可以同时进行。
• 注意判断链表长度为奇数的时候，对比两个链表之时，要跳过最中间的节点，此时要跳过中间节点。

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        //cur指向当前要反转的节点，dummy作为头插法的头
        ListNode cur = head, dummy = new ListNode();
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            //反转
            cur.next = dummy.next;
            dummy.next = cur;
            cur = slow;
        }
        //此时链表长度为奇数，应该跳过中心节点
        if (fast != null) slow = slow.next;
        dummy = dummy.next;
        //此时dummy指向反转后链表的头，slow指向后半部分链表的头，开始比较
        while (slow != null && dummy != null){
            if (slow.val != dummy.val){
            	//如果不相等，返回否
                return false;
            }
            slow = slow.next;
            dummy = dummy.next;
        }
        return true;
    }
}