题解 | #链表分割#

1.思路

• 1.先通过快慢指针，找到中间结点
• 2.对中间结点后面的链表进行反转
• 3.指针从两端开始移动，如果符合回文结构，在奇数情况下相与，在偶数情况下相邻

2.图解

3.解题步骤

• 1.判断头结点是否为空，判断是否只有一个结点
• 2.设立快慢指针，找到中间的结点
• 3.设cur结点为中间结点的下一个结点,进行后面链表的反转
• 4.当cur为空时，说明slow到了末尾
• 5.让头结点和slow向中间移动
• 6.如果两端的值不等时，直接返回false
• 7.在奇数个结点的情况下，head和slow相遇
• 8.在偶数结点的情况下，head的下一个结点就是slow

4.代码

public boolean chkPalindrome() {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        //寻找中间结点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //翻转
        ListNode cur = slow.next;//cur代表当前需要翻转的结点
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //一个从前往后，一个从后往前，进行比较， 直到slow和head相遇
        while (slow != head) {
            if (head.val != slow.val) {
                return false;
            }
            if (head.next == slow) {//走到这里两个val值一样，偶数情况
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }