leetcode-234 回文链表(PalindromeLinkedList)-java

题目：回文链表

请检查一个链表是否为回文链表。

进阶：

你能在 O(n) 的时间和 O(1) 的额外空间中做到吗？

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null)
        return true;
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode reverseHead = reverseList(slow.next);

    while (head != null && reverseHead != null) {
        if (head.val != reverseHead.val)
            return false;
        head = head.next;
        reverseHead = reverseHead.next;
    }
    return true;
}

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode p = null;
    ListNode q;
    while (head != null) {
        q = head.next;
        head.next = p;

        p = head;
        head = q;
    }
    return p;
}

边界值判断：

head == null    // 空链表，回文，返回true

head.next == null    // 只有一个节点的链表，回文，返回true

变量注释：

fast    // 快指针，初始化为head

slow    // 慢指针，初始化为head

reverseHead    // 后半链表反转后的头结点

解题思路：

（1）利用快慢指针找到链表中点(后半链表的头结点)    // 链表长度为n，后半链表的头节点为(n+1)/2 + 1;

（2）反转后半链表，拿到反转后的链表的头节点    // 对反转链表有疑问的，点击 反转链表 了解详情

（3）前半段链表  与  反转后的后半段链表  依次进行比较，都相等就是回文链表    // 链表长度为奇数时，忽略前半段链表的最后一个节点