题解 | #判断一个链表是否为回文结构#

策略

1. 快慢指针，找到后半部分起点 slow
2. 后半部分反转，避免破坏整个链表
3. 反转后前后对比

public class Solution {
    public boolean isPail(ListNode head) {
        if (head == null || head.next == null) {
            return true; // 空链表或者只有一个节点的链表都是回文链表
        }

        // 使用快慢指针找到链表的中间点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转整个链表的问题在于，反转后整个链表的结构会被破坏，而我们需要的是只反转链表的后半部分，以便与前半部分进行比较。
        // ListNode reversedSecondHalf = reverseList(head);

        // 反转后半部分链表
        ListNode reversedSecondHalf = reverseList(slow);

        // 比较前半部分和后半部分
        ListNode firstHalf = head;
        ListNode secondHalf = reversedSecondHalf;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false; // 不相等，说明不是回文链表
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true; // 所有节点都相等，说明是回文链表
    }

    // 反转链表的方法
    // private ListNode reverseList(ListNode head) {
    //     ListNode prev = null;
    //     ListNode curr = head;
    //     while (curr != null) {
    //         ListNode next = curr.next;
    //         curr.next = prev;
    //         prev = curr;
    //         curr = next;
    //     }
    //     return prev;
    // }
    private ListNode reverseList(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode ref1 = null;
        ListNode ref2 = pHead;
        ListNode ref3;

        while (ref2 != null) {
            ref3 = ref2.next;
            ref2.next = ref1;
            ref1 = ref2;
            ref2 = ref3;
        }
        return ref1;
    }
}