如何高效判断回文链表 :: labuladong的算法小抄

[utterances-bot]

如何高效判断回文链表 :: labuladong的算法小抄

https://labuladong.gitee.io/algo/2/17/18/

[AVAL-NIX]

while (right != null) { 这里还要判断一下 left!=null

[JewinH]

if (fast != null) slow = slow.next;

这里要判断slow.next != null ，如果输入只有一个元素，可能会出现slow.next = null 的情况，导致slow.val 出错。

[Yuyan9618]

赞赞赞！写的太好了

[keeleys]

下面这个不判断，好像也行。

if (fast != null)
    slow = slow.next;

1-2- 3-2-1-null 反转后的两条分别是 1-2-3-null 1-2-3-null 不加也行的。

[jungle8884]

public boolean isPalindrome2(ListNode head) {
        // 先通过双指针找到链表的中点
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow 指向链表中点
        // 如果fast指针没有指向null, 说明链表长度为奇数, slow还要再前进一步
        if (fast != null) {
            slow = slow.next;
        }

        // 用于恢复链表结构的指针
        ListNode p, q;

        // 从slow开始反转后面的链表, 开始比较回文串
        ListNode left = head;
        ListNode right = reverse(slow);
        p = left; q = right;
        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            p = left;
            left = left.next;
            right = right.next;
        }

        p.next = reverse(q);
        return true;
    }

[SharkLJ]

请问如果要恢复链表结构，如何得到p，q的位置？

[tt110617]

请问如果要恢复链表结构，如何得到p，q的位置？

仅供参考

 public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        // 恢复链表结构
        ListNode p = null, q = null;
        // slow 指向链表中点
        while (fast != null && fast.next != null) {
            p = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        // 说明链表有奇数个节点，slow需要再进一步
        if (fast != null) {
            p = slow;
            slow = slow.next;
        }
        ListNode left = head;
        // 局部反转链表
        ListNode right = reverse(slow);
        q = right;
        while (right != null) {
            // 判断是否为回文串
            if (left.val != right.val) {
                // 当链表没有节点或只有一个节点时，不需要恢复链表
                if (p != null && p != q) {
                    p.next = reverse(q);
                }
                return false;
            }
            left = left.next;
            right = right.next;
        }
        if (p != null && p != q) {
            p.next = reverse(q);
        }
        return true;
    }

[gcdd1993]

简单易懂，赞！

[Goolloo]

捉个小虫，最后恢复后一半链表的时候不需要更改前一半的最后一个node。也就是相对于q.next = reverse(headOfReversedSecondHalf)，直接使用reverse(headOfReversedSecondHalf)。 根据你画的反转过的链表图，其实前一半最后一个节点一直指向第二半的第一个节点。

1→2→3→4→3→2→1

↓

1→2→3→4→3←2←1

所以最后只需要再次把后一半链表反转足矣

boolean isPalindrome(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if (fast != null)
        slow = slow.next;
    
    ListNode left = head;
    //----
    ListNode headOfReversedSecondHalf = reverse(slow);
    //----
    ListNode right = headOfReversedSecondHalf;
    while (right != null) {
        if (left.val != right.val)
            return false;
        left = left.next;
        right = right.next;
    }

    //----
    // recover 2nd half
    reverse(headOfReversedSecondHalf);
    //----

    return true;
}