剑指 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, 105]
  • 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;
}