题解 | #判断一个链表是否为回文结构#找中点的同时反转

思路

• 双指针找中点，遍历同时反转前半部分
• 处理特殊情况
• fast指针回到反转后的头指针的位置，与slow指针逐个比较

实现

import java.util.*;

public class Solution {
    public boolean isPail (ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = null;
        // 找到中点的同时，反转前面部分
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            ListNode tmp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = tmp;
        }
        // 奇数个结点时，slow指针得往后移一位，以当做后半部分的起点
        if(fast.next == null) {
            slow = slow.next;
        }else { // 偶数个时，得多往后反转一个
            ListNode tmp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = tmp;
        }
        fast = pre;
        while(slow != null) {
            if(slow.val != fast.val) return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
}