0

以下は、リンクされたリストを逆にする私のコードです:

public LinkedList reverse() {
    LinkedList m = new LinkedList();
    Node temp = this.getHeadNode();
    while(temp!= null) {
        m.insertFirst(temp.getElement());
        temp = temp.getNext();
    }
    m.getTailNode().setNext(null);
    return m;
}

私の関数で宣言されたローカル変数 LinkedList mi について、それは私が O(n) 量の追加スペースを使用していることを意味しますか、それとも一定量のスペースと見なされますか?

4

5 に答える 5

1

こんにちは、セカンダリ リストを作成せずにリンク リストを逆にすることも、より良い方法の 1 つだと思います。

于 2012-09-11T04:28:47.000 に答える
1

3 つのポインターを取り、開始時に 3 つすべてを初期化します。これらのポインターが x、y、z であると仮定してから、y=x->next、z=y->next 、y->next=x、x=y に移動します。x がリストの最後に達するまでこれを行います。

于 2012-09-11T04:49:03.980 に答える
0

リンクリストの新しいインスタンスを作成しているので、メモリにリストのコピーが2つあります。リストにはオブジェクトへの参照が含まれるため、オブジェクトのインスタンスをカウントする場合は安全であり、追加のメモリの量はO（1）です。ただし、リスト自体にはある程度のメモリが必要です。したがって、リスト内の「セル」の数を数えると、そうです。O（N）個の追加メモリが使用されています。

于 2012-09-11T04:09:32.240 に答える
0

これは私がしたことです：

public LinkedList reverse1() {
    Node temp1 = tail;
    Node temp2 = head;
    Node temp3 = new Node(this.removeFirst());
    temp1.setNext(temp3);
    temp3.setNext(null);
    //head = temp1;
    tail = temp3;
    while(head != temp1) {
        temp2 = new Node(this.removeFirst());
        temp2.setNext(temp3);
        temp1.setNext(temp2);
        temp3 = temp2;
    }
    return this;
}

これで十分ですか？

于 2012-09-11T04:47:35.983 に答える