234. 回文链表

回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用  O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解析：见 org 第三种解法
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // org 时间空间复杂度都是 O(n)
    // equals [-129,-129]
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> res    = new ArrayList<Integer>();
        ListNode cur = head;
        while(cur != null)&#123;
            res.add(cur.val);
            cur = cur.next;
        &#125;
        int front=0;
        int tail =res.size()-1;
        while(front<=tail)&#123;
            if(!res.get(front).equals(res.get(tail)))&#123;
                return false;
            &#125;
            front++;
            tail--;
        &#125;
        return true;
    &#125;

    // //第一次 提交 针对奇数个元素 不成立。
    // public boolean isPalindrome(ListNode head) &#123;
    //     if(head==null)&#123;
    //         return false;
    //     &#125;
    //     Stack<Integer> res    = new Stack<Integer>();
    //     ListNode cur = head;
    //     while(cur!=null)&#123;
    //         if(!res.isEmpty()&&res.peek() == cur.val)&#123;
    //             res.pop();
    //         &#125;
    //         else&#123;
    //             res.add(cur.val);
    //         &#125;
    //         cur = cur.next;
    //     &#125;
    //     return res.isEmpty();
    // &#125;
&#125;