BM13. [判断一个链表是否为回文结构]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM13. 判断一个链表是否为回文结构

https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f?tpId=295&sfm=github&channel=nowcoder

题目分析
首先大家要了解什么是回文结构，这道题目推荐使用额外的空间stack进行解决。链表的顺序刚好和栈的弹出顺序的相反的可以用来判断回文结构。

做法分析

第一步数组进行进栈操作

Stack<ListNode> stack = new Stack<>();
ListNode tmpHead = head;
while(tmpHead != null){
stack.add(tmpHead);
    tmpHead = tmpHead.next;
}

遍历进行比较，如果存在不相等的情况，那么证明就不是回文结构则返回false，反之则返回true

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

全部题解

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

复杂度分析

时间复杂度：遍历列表
空间复杂度：需要额外开辟空间stack存储一遍列表