BM13. [判断一个链表是否为回文结构]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM13. 判断一个链表是否为回文结构
题目分析
首先大家要了解什么是回文结构，这道题目推荐使用额外的空间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存储一遍列表
