剑指 Offer II 027. 回文链表

题目

给定一个链表的头节点head，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

flowchart LR
1A((1)) --> 2A((2)) --> 3((3)) --> 2B((2)) --> 1B((1))

输入: head = [1,2,3,3,2,1]
输出: true

示例 2：

flowchart LR
1((1)) --> 2((2))

输入: head = [1,2]
输出: false

提示：

链表 L 的长度范围为 [1, 10⁵]
0<= node.val <= 9

进阶：能否用O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

注意：本题与主站234题相同

题解

public boolean isPalindrome(ListNode head) {
    // 快慢指针找中间节点
    ListNode slow = new ListNode(0, head), fast = slow;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 中间节点链表
    ListNode mid = slow.next;
    slow.next = null;
    // 链表倒置
    ListNode right = new ListNode(0), t;
    while (mid != null) {
        t = mid.next;
        mid.next = right.next;
        right.next = mid;
        mid = t;
    }

    // 判断是否回文
    right = right.next;
    while (right != null) {
        if (right.val != head.val) {
            return false;
        }

        right = right.next;
        head = head.next;
    }

    return true;
}