/*

    快慢指针得到链表中间，然后用206题方法反转后半部分，然后比较

     */

    public class ListNode {

        int val;

        ListNode next;

        ListNode(int x) { val = x; }

    }

    public boolean isPalindrome(ListNode head) {

        //快慢指针

        ListNode slow = head,fast = head;

        while (fast!=null&&fast.next!=null)

        {

            slow = slow.next;

            fast = fast.next.next;

        }

        //节点如果是奇数，fast应该不是null，如果是偶数就是null

        if (fast!=null)

        {

            slow = reverseList(slow.next);

        }

        else slow = reverseList(slow);

        while (slow!=null)

        {

            if (head.val!=slow.val) return false;

            slow = slow.next;

            head = head.next;

        }

        return true;

    }

    public ListNode reverseList(ListNode head) {

        ListNode pre = null;

        while (head!=null)

        {

            //下边要改变head，所以先保存下来next

            ListNode next = head.next;

            //将当前节点指向pre

            head.next = pre;

            //更新pre

            pre = head;

            //更新head往下遍历

            head = next;

        }

        return pre;

    }