回文链表

理解题目：

题目要求判断一个单链表是否是回文链表，即链表正序和逆序遍历得到的序列相同。

代码实现：

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

        // 找到链表的中点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

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

        // 比较前半部分链表和反转后的后半部分链表
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        while (p2 != null) {
            if (p1.val != p2.val) {
                // 恢复后半部分链表的顺序
                slow.next = reverseList(secondHalfStart);
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 恢复后半部分链表的顺序
        slow.next = reverseList(secondHalfStart);
        return true;
    }

    // 反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        return prev;
    }
}

步骤解释：

如果链表为空或只有一个节点，则认为是回文链表，直接返回 true。
使用快慢指针找到链表的中点，慢指针 slow 每次移动一步，快指针 fast 每次移动两步，当 fast 到达链表末尾时，slow 正好指向链表的中点。
反转后半部分链表，并返回反转后的头节点。
比较前半部分链表和反转后的后半部分链表，如果有节点值不相等，则说明不是回文链表，返回 false；否则继续比较直到链表末尾。
恢复后半部分链表的顺序。
如果比较过程中没有返回 false，则链表是回文链表，返回 true。

时间复杂度： 遍历链表两次，时间复杂度为 O(n)，其中 n 是链表的长度。

空间复杂度： 除了常数级别的额外空间，还使用了递归调用的栈空间，因此空间复杂度为 O(n)。