234 回文链表

输入: 1->2
输出: false

输入: 1->2->2->1
输出: true

public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList();
    // 将链表的值复制到数组中
    ListNode cur = head;
    while (cur != null) {
        vals.add(cur.val);
        cur = cur.next;
    }
    // 使用双指针判断是否回文
    int length = vals.size();
    for(int i = 0, j = length -1; i < length/2; i++,j--){
        int val1 = vals.get(i);
        int val2 = vals.get(j);
        if( val1 != val2 ) return false;
    }
    return true;
}

public boolean isPalindrome(ListNode head) {
    ListNode fast = head; 
    ListNode slow = head;
    //通过快慢指针找到中点
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //如果fast不为空，说明链表的长度是奇数个
    if (fast != null) {
        slow = slow.next;
    }
    //反转后半部分链表
    slow = reverseList(slow);
    fast = head;
    while (slow != null) {
        //然后比较，判断节点值是否相等
        if (fast.val != slow.val) return false;
        fast = fast.next;
        slow = slow.next;
    }
    return true;
}
//反转链表
public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode next = null;
    while( cur != null){
        //记住原链表的下一个
        ListNode temp = cur.next;
        //设下next
        cur.next = next;
        //更新next与cur
        next = cur;
        cur = temp;
    }
    return next;
}