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

alt

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存储一遍列表

alt

#面经##题解##面试题目#
全部评论

相关推荐

兄弟们,实习都是在接各种api,该怎么包装简历
仁者伍敌:感觉我自己做小项目也是各种api啊,我要怎么包装简历
点赞 评论 收藏
分享
点赞 评论 收藏
分享
05-19 15:21
已编辑
门头沟学院 Java
白火同学:你才沟通了200,说实话,北上广深杭这里面你连一座城市的互联网公司都没投满呢,更别说还有各种准一线二线城市了。等你沟通突破了三位数,还没结果再考虑转行的事吧。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务