1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public boolean isPail (ListNode head) {
        // 空链表 或 单节点链表 一定是回文链表
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 找链表中点：快指针走2步，慢指针走1步
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 链表长度为奇数时，跳过正中间的节点
        if (fast != null) {
            slow = slow.next;
        }
        // 快指针重置为链表头，慢指针指向反转后的后半段链表头
        fast = head;
        slow = reverseList(slow);
        // 双指针逐一比对前后两段链表的节点值
        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        // 所有节点值都相等，是回文链表
        return true;
    }

		// 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;  // 保存下一个节点
            cur.next = pre;   // 反转当前节点的指针指向
            pre = cur;        // 前驱节点向后移动
            cur = next;       // 当前节点向后移动
        }
        return pre; // 返回反转后的链表头节点
    }