/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        //思路：创建一个链表和原链表相同，再翻转，然后比较；两条链表
        if (head == null) {
            return true;
        }
        ListNode headNew = new  ListNode(head.val);
        ListNode curNew = headNew;
        ListNode cur = head;
        while (cur.next != null) { // 复制链表
            curNew.next = new ListNode(cur.next.val);
            cur = cur.next;
            curNew = curNew.next; 
        } 
        ListNode pre = null;
        curNew = headNew;
        while (curNew != null) {    // 翻转链表
            ListNode tmp = curNew.next;
            curNew.next = pre;
            pre = curNew;
            curNew = tmp;
        }
        curNew = pre;
        cur = head;
        while (curNew != null) {
            if (curNew.val != cur.val) {
                return false;
            } else {
                curNew = curNew.next;
                cur = cur.next;
            }

        }
        return true;    
    }
}