234. 回文链表

佚名 5年前 (2019-06-02) 算法 1686人围观抢沙发百度已收录

请判断一个链表是否为回文链表。

示例 1:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入: 1->2
输出: false

示例 2:

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

解答：将链表的前半部分入栈，然后再从链表的后半部分开始遍历，遍历一个出栈一次，如果相等继续遍历，不等就说明不是回文串，返回false即可。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        Stack<ListNode> stack = new Stack<>();
        ListNode p1 = head;
        ListNode p2 = head;
        while(p2!=null && p2.next!=null){
            stack.push(p1);
            p1 = p1.next;
            p2 = p2.next.next;
        }
        if(p2!=null) p1 = p1.next;
        while(p1!=null){
            if(stack.pop().val!=p1.val){
                return false;
            }
            p1 = p1.next;
        }
        return true;
    }
}