NC96：判断一个链表是否为回文结构

解法1：栈
利用栈结构，从左到右遍历链表，遍历的过程中把每个节点依次压入栈中。因为栈是先进后出的，所以遍历完成后从栈顶到
栈的节点值顺序会与原链表从左到右的值是顺序反过来的。那么如果一个链表是回文结构的话逆序之后值出现的顺序是一样的
如果不是回文结构，顺序就肯定对不上
----额外空间复杂度为O(n)

    public boolean isPail (ListNode head) {
        // write code here
        Stack<ListNode> stack=new Stack<ListNode>();
        ListNode cur=head;
        while(cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while(head!=null){
            if(head.val!=stack.pop().val){
                return false;
            }
            head=head.next;
        }
        return true;
    }

解法2：快慢指针+翻转
将后半部分的链表倒置，然后这个链表链表分别从两点开始遍历，对比元素是否是相等;

    public boolean isPail (ListNode head) {
        if (head == null || head.next == null)
            return true;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode reverseHead = reverseList(slow.next);

        while (head != null && reverseHead != null) {
            if (head.val != reverseHead.val)
                return false;
            head = head.next;
            reverseHead = reverseHead.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode p = null;
        ListNode q;
        while (head != null) {
            q = head.next;
            head.next = p;
            p = head;
            head = q;
        }
        return p;
    }

解法3：快慢指针+栈
使用一个快慢指针，找到链表的中间位置，从中间位置开始遍历后面的数据，并逐一将数据入栈。然后将栈中数据与链表前半部分相比较，只要中途出现不一样就返回false，否则返回true。
---额外空间复杂度为O(n/2)

    public boolean isPail (ListNode head) {
        // write code here
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        Stack<ListNode> stack=new Stack<ListNode>();
        while(slow!=null){
            stack.push(slow);
            slow=slow.next;
        }
        while(!stack.isEmpty()){
            if(stack.pop().val!=head.val){
                return false;
            }
            head=head.next;
        }
        return true;
    }

解法4：list
使用数组把节点值存起来，再比较

   public boolean isPail (ListNode head) {
        // 最笨的办法
        ArrayList<Integer> list = new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }

        int l=0,h = list.size()-1;
        while(l<h){
            if(!list.get(l).equals(list.get(h))){ //这个地方返回的是Integer对象，不能使用==
                return false;
            }
            l++;
            h--;
        }
        return true;
    }