234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
输入：head = [1,2,2,1]
输出：true

示例 2：
输入：head = [1,2]
输出：false

可以借用一下集合，集合可以通过索引从两头向中间一一遍历元素，遍历的同时就可以一一比较元素值是否相同：

public boolean isPalindrome(ListNode head) {
    List<Integer> valList = new ArrayList<>();
    // 遍历链表，将节点放入 List
    ListNode cur = head;
    while (cur != null) {
        valList.add(cur.val);
        cur = cur.next;
    }
    // 双指针从 List 两头同时遍历并比较是否相同
    int left = 0;
    int right = valList.size() - 1;
    while (true) {
        // 走到同一个节点，表示链表的节点数量是奇数
        if (left == right) {
            return true;
        }
        // 左指针走到了右指针后侧，表示链表的节点数量是偶数
        if (left > right) {
            return true;
        }
        // 只要有某个值不同，则表示不是回文链表
        if (!valList.get(left).equals(valList.get(right))) {
            return false;
        }
        left++;
        right--;
    }
}

通过集合的思路，如果直接在链表中能够也找到两个指针，那么是否也可以达到相同的效果呢？

假设链表的节点数量是偶数：

假设链表的节点数量是奇数：

而 876. 链表的中间结点 情况和上述类似：
1）链表的节点数量是奇数时，和上述节点数量是奇数的情况一致
2）链表的节点数量是偶数时，和上述节点数量是偶数的情况稍稍有点不同，上述情况找的是链表前半部分的最后一个节点，而在链表的中间结点中是链表后半部分的第一个节点

/**
 * 找到链表中点
 * 节点数量是奇数时，则刚好是中间节点
 * 节点数量是偶数时，则刚好是后半部分第一个节点
 * @param head
 * @return
 */
public ListNode middleNode(ListNode head) {
    // 快慢指针都指向头结点
    ListNode fast = head;
    ListNode slow = head;
    // 快指针或者快指针的下一个节点是 null 时
    while(fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
}

稍稍改动一下上述算法：

/**
 * 找到链表中点
 * 节点数量是奇数时，则刚好是中间节点
 * 节点数量是偶数时，则刚好是前半部分最后一个节点
 * @param head
 * @return
 */
public ListNode middleNode(ListNode head) {
    // 快慢指针都指向头结点
    ListNode fast = head;
    ListNode slow = head;
    // 快指针的下一个节点或者下下一个节点是 null 时
    while (fast.next != null && fast.next.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

那么直接利用双指针算法如下：

public boolean isPalindrome(ListNode head) {
    if (head == null) {
        return true;
    }
    // 找到前半部分链表的尾节点并反转后半部分链表
    ListNode firstHalfEnd = endOfFirstHalf(head);
    ListNode secondHalfStart = reverseList(firstHalfEnd.next);
    // 判断是否回文
    ListNode slow = head;
    ListNode fast = secondHalfStart;
    boolean isPalindrome = true;
    while (isPalindrome && fast != null) {
        if (slow.val != fast.val) {
            isPalindrome = false;
        }
        slow = slow.next;
        fast = fast.next;
    }
    // 还原链表并返回结果
    firstHalfEnd.next = reverseList(secondHalfStart);
    return isPalindrome;
}
/**
 * 找到链表前半部分最后一个节点
 *
 * @param head
 * @return
 */
public ListNode endOfFirstHalf(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
/**
 * 反转链表
 * 
 * @param head
 * @return
 */
public 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;
}