leetcode-回文链表

leetcode-回文链表 题目：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解法一（利用栈）：

    
    public boolean isPalindrome(ListNode head) {
        if (head.next == null){
            return true;
        }
        //使用栈来处理
        Stack stack = new Stack<>();

        List list = new ArrayList<>();

        ListNode cur = head;//辅助节点，用来遍历链表

        while (cur != null){
            list.add(cur.val);
            cur = cur.next;
        }

        //偶数情况
        if (list.size()%2 == 0){
            for (int i = 0 ; i < list.size()/2 ; i++){
                stack.push(list.get(i));
            }
            for (int i = list.size()/2; i < list.size() ; i++){
                if (list.get(i) != stack.peek()){
                    return false;
                }else stack.pop();
            }
        }
        //奇数情况
        if (list.size()%2 == 1){
            for (int i = 0 ; i < (list.size()-1)/2 ; i++){
                stack.push(list.get(i));
            }
            for (int i = (list.size()+1)/2; i < list.size() ; i++){
                if (list.get(i) != stack.peek()){
                    return false;
                }else stack.pop();
            }
        }
        return stack.empty();
    }

解法二（双指针）：

  
    public boolean isPalindrome(ListNode head) {

        List list = new ArrayList<>();

        ListNode cur = head;

        while (cur != null){
            list.add(cur.val);
            cur = cur.next;
        }

        int front = 0;//前指针
        int rear = list.size()-1;//后指针

        while (front < rear){
            if (list.get(front) != list.get(rear)){
                return false;
            }
            front++;
            rear--;
        }
        return true;
    }