1

このアルゴリズムの複雑さは? 私はそれがO(N)だと仮定していますが、明確にしたいと思います。リンクされたリストに末尾がある場合、リストの最後までループする while(current != null) ループを完全に回避するため、これはさらに高速になると思います。

public void reverse() {
    Stack<Node> stack = new Stack<Node>();
    if (this.head != null || this.head.next != null) {
        Node current = this.head;
        while (current != null) {
            stack.push(current);
            current = current.next;
        }
        Node last = null;
        while (!stack.empty()) {
            if (last==null) {
                this.head = stack.pop();
                last = this.head;
                continue;
            }
            last.next = stack.pop();
            last = last.next;
            if (stack.empty()) {
                last.next = null;
            }
        }
    }
}
4

2 に答える 2

3

これは1つのNであるリストを反復することにより、すべてのリンクされたリスト要素をスタックにプッシュします。次に、別のNであるスタックを反復するため、O(2N)で順序表記を行います

O(1) スペースと O(n) 時間でリストを反転する方法を参照してください。

于 2012-08-16T22:15:21.923 に答える
1

アルゴリズムはクラス O(N) です。静的量の操作 (最初のループ) の N 倍を使用し、次に静的量の操作 (2 番目のループ) を使用しています。Stack.pop() は "N" から独立している必要があります。つまり、これはクラス O(2N+c) にあり、O(2N+c) は O(N) にあるクラス O(2N) にあることを意味します。つまり、ルーチンの実行時間は、スタック内の要素の数に比例して増加します。

または単に: はい、クラス O(N) にあります。

于 2012-08-16T22:24:57.723 に答える