LeetCode-234-回文链表

题目

思路

1. 链表不是回文的，指其中的数字有可能会回文。最直接的方法是遍历加入数组然后判断数组回不回文即可，但是这样的话太暴力了应该不是他们想要的解法。
2. 回文的开始有一个特征：下一个和自己相等。
3. 不对，也有可能不相等，但是根据中间的节点对称…
4. 突然想到是否能够用栈，将遍历的数字压入栈中，再从头开始遍历的同时弹出栈，判断数字相不相等就行了。不过总感觉和最暴力的解法差不多。

代码

    public boolean isPalindrome(ListNode head) {
    
        Stack<Integer> s = new Stack<>();
        ListNode temp = head;
        while(temp!=null){
    
            s.push(temp.val);
            temp=temp.next;
        }
        //开始对比 重新遍历
        while(head.next!=null){
    
            if(head.val!=s.pop()) return false;
            head=head.next;
        }
        return true;
    }