234. 回文链表

双指针（快慢指针）

这道题用到了25题的reverse函数，梦幻联动哈哈。
步骤：

1. 用双指针，快慢指针，先找到中点、

1. 如果fast没有指向null，说明链表长度为奇数， slow指针需要再前进一步

1. 从slow指向的节点开始，反转后面的链表。然后开始比较回文，比较回文的代码就是很经典的比较，左指针就是head，右指针就是reverse之后返回的head，之后循环比较，循环的条件是右指针不为null，如果左右指针的val不同则不是回文，如果通过循环则是回文。

//输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点
public ListNode reverse(ListNode head) {
    //前一个、当前、后一个节点
    ListNode pre = null, cur = head, nxt = head;
    while(cur != null){
        nxt = cur.next;
        //逐个节点反转
        cur.next = pre;
        //更新指针位置
        pre = cur;
        cur = nxt;
    }
    //返回反转后的头节点
    return pre;
}
public boolean isPalindrome(ListNode head) {
    //初始化快慢指针
    ListNode slow, fast;
    slow = fast = head;
    //快指针每次移动2格，慢指针每次1格，当快指针指向null时，slow指针指向中点
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    //如果fast没有指向null，说明链表长度为奇数，slow还要再前进一步：
    if(fast != null){
        slow = slow.next;
    }
    //将从slow节点开始的链表反转，并将反转之后的头节点作为right
    ListNode left = head;
    ListNode right = reverse(slow);
    //每次比较left和right是否相同，不相同则不是回文
    while(right != null){
        if(left.val != right.val){
            return false;
        }
        left = left.next;
        right = right.next;
    }
    return true;
}