剑指offer-从头到尾打印链表
2021/9/16 23:08:43
本文主要是介绍剑指offer-从头到尾打印链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题源剑指offer
剑指Offer_在线编程+题解_牛客题霸_牛客网
在牛客网的解答里,有的高赞有多种答案,写完了栈的方式后和其对照,发现其使用ArrayList的方法是不适合的。复杂度来到了O(n2)。很显然,是在分析复杂度时,没有考虑到ArrayList自带的add(index , val);其底层实现并不是链表,而是数组,导致其每添加一次就得使元素后退一位,故其复杂度大大提高。从实践中也可以看出
使用Stack完成该基础的操作,100w的长度只需80ms
而使用ArrayList,2259ms才操作完10w个数据。
package 剑指Offer.从头到尾打印链表 import java.util.ArrayList; import java.util.Stack; /** * @program:多线程和IO * @descripton: * @author:ZhengCheng * @create:2021/9/16-13:12 **/ public class s { //测试第一种,使用stack public static void main(String[] args) { Node head = new Node(1, null); Node temp = head; for (int i = 2; i < 1000000; i++) { temp.next=new Node(i,null); temp = temp.next; } //链表已组装完成 //MethodStack long l = System.currentTimeMillis(); /* Node[] nodes = methodStack(head); 80ms 跑完100w*/ Node[] nodes = methodArray(head); //2259ms 10w long l1 = System.currentTimeMillis(); for (int i = 0; i < nodes.length; i++) { System.out.println(nodes[i].id); } System.out.println(l1-l);//80 } private static Node[] methodStack(Node head) { Stack stack = new Stack(); Node temp = head; int cnt = 0; while (temp!=null){ stack.push(temp); temp=temp.next; cnt++; } Node[] nodes = new Node[cnt]; for (int i = 0; i < cnt; i++) { nodes[i] = (Node) stack.pop(); } return nodes; } private static Node[] methodArray(Node head){ ArrayList<Node> nodes = new ArrayList<>(); Node temp = head; int cnt = 0; while (temp!=null){ nodes.add(0,temp); temp=temp.next; cnt++; } Node[] nodes1 = new Node[cnt]; for (int i = 0; i < cnt; i++) { nodes1[i] = nodes.remove(0); } return nodes1; } } class Node{ public int id; public Node next ; public Node() { } public Node(int id,Node next ) { this.next = next; this.id = id; } }
这篇关于剑指offer-从头到尾打印链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-19JAVA 企业级项目入门:从零开始的实战指南
- 2024-09-19Java 企业级项目入门:从零基础到实战的进阶之路
- 2024-09-19Java 企业级项目入门:从零开始的实战指南
- 2024-09-18Java OA系统入门:从基础到实践
- 2024-09-18Java OA系统入门:从零开始的简单教程
- 2024-09-18JAVA OA系统入门:从零开始的实战指南
- 2024-09-18Java Web项目入门:快速搭建你的第一个Web应用
- 2024-09-18JAVA web项目入门:从零基础到实战的小白指南
- 2024-09-18Java Web项目入门:从零开始的轻量级教程
- 2024-09-18Java Web项目入门:快速搭建与基础实践