gold-2-6

编写一个函数，检查输入的链表是否是回文的。

示例 1：

输入： 1->2
输出： false 

示例 2：

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

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        List<Integer> reverseList = new ArrayList<>();
        getList(head, reverseList);

        ListNode temp = head;
        int index = 0;
        int len = reverseList.size() / 2;
        while (index <= len) {
            if (temp.val != reverseList.get(index)) {
                return false;
            }
            temp = temp.next;
            index++;
        }
        return true;
    }

    void getList(ListNode head, List<Integer> reverseList) {
        if (head.next == null) {
            reverseList.add(head.val);
        } else {
            getList(head.next, reverseList);
            reverseList.add(head.val);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)