题源剑指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;
    }
}