0

リンクリストの私の実装では、2つの方法があります。一方のメソッドを呼び出すと、もう一方のメソッドの結果に影響します。1つの方法はconcatenateLL()、2つのリストを連結することであり、1つの方法はgetNumberOfNodes()、リンクリスト内のノードの数を返すことです。私のメソッド連結では、2つのリストを連結した新しいリストを返すことになっています。しかし、私のコードでは、結果の新しいリストは最初のパラメーターのリストに影響を与えます。lリストとパラメータを渡しm、新しいリストを返すとします。

問題は、新しいものが単なるリストlであり、リストの要素が含まれていることですm（連結のため）。getNumberOfNodes()このため、リストlとを呼び出すとm、間違った値が返されます。

これが私のコードです：

public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
    LinkedList a = l;
    Node l_last = a.getTailNode();
    Node m_first = m.getHeadNode();
    l_last.setNext(m_first);
    a.tail = m.getTailNode();
    return a;
}

public int getNumberOfNodes(Node h) {
    if(h == null)
        return 0;
    return 1 + getNumberOfNodes(h.getNext());
}

public static void print(LinkedList l) {
    Node v = l.getHeadNode();
    while(v != null) {
        System.out.print(v.getElement()+" ");
        v = v.getNext();
    }
    System.out.println();
}

public static void main(String[] args) throws IndexOutOfBoundsException {
    // TODO Auto-generated method stub
    LinkedList l = new LinkedList();
    LinkedList m = new LinkedList();
    l.insertFirst(5);
    l.insertFirst(7);
    l.insertFirst(3);
    l.insertFirst(6);
    print(l);
    m.insertFirst(2);
    m.insertFirst(4);
    m.insertFirst(9);
    m.insertFirst(8);
    m.insertLast(10);
    m.insertLast(12);
    print(m);
    LinkedList n = concatenateLL(l, m);
    print(n);
    System.out.println(l.getNumberOfNodes(l.getHeadNode()));
    System.out.println(m.getNumberOfNodes(m.getHeadNode()));
}

mainメソッドでは、listの長さがl返さ4れ、listmが返される必要があり6ます。しかし、を呼び出す前に連結メソッドを呼び出した後、asの長さ（との連結の結果としてのリストのノードの数）とasの長さ（理由はわかりません）getNumberOfNodes()を取得します。l10nlmm15

4

3 に答える 3

1

私があなたのコードを見るとき、私はあなたがC / C ++で書くことに慣れていると思います（命名規則と予想される振る舞いに基づいています）。あなたの問題は深いコピーを作ることにあります。メソッドの最初に、両方のconcatenateLLリストのディープコピーを作成する必要があります。その後、現在の方法でそれらを連結できます。

LinkedList a = l; // problem line

C / C ++ではコピーコンストラクターを呼び出しますが、Javaにはそのようなものがないため、自分で実装する必要があります。clone()によって宣言されたメソッドを使用してオーバーライドできますが、リストだけでなくノード間の参照も変更するため、浅いものではなく深いコピーjava.lang.Objectを作成する必要があります。

たとえば、メソッドは次のようになります。

public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
   LinkedList a = new LinkedList();

   // copy Nodes, you need to create new instance of them
   for ( int i = 0; i < l.getNumberOfNodes(l.getHeadNode()); ++i )
        a.insertLast( l.getNode( i ) );

   // copy Nodes, you need to create new instance of them
   for ( int i = 0; i < m.getNumberOfNodes(m.getHeadNode()); ++i )
        a.insertLast( m.getNode( i ) );

   return a;
}

ただし、メソッドがであるため、この実装はO(n^2)複雑であることに注意する必要があります。より良い解決策はイテレータを使用することですが、クラスがそれを実装しているかどうかはわかりません。getNode()O(n)

編集： 複雑さを改善するためにO(n)、標準のインターフェイスIteratorを実装することをお勧めします。とにかく重要なのは、現在の要素への参照を維持して、次の要素を簡単に取得できるようにすることです。簡単な例を挙げれば：

Node item = l.getHeadNode();

while( item != null ) {
    // copy the item
    a.insertLast( item );
    item = item.getNext();
}

そして、リストについても同じですm。

于 2012-09-12T05:36:41.197 に答える
0

はい、LInkedList a = l;リンクリストのコピーは作成されませんl。

を変更したくない場合は、新しいリンクリストを作成する必要がありますl。

于 2012-09-12T05:38:42.237 に答える
0 
public static LinkedList concatenateLL(LinkedList l, LinkedList m) {
    LinkedList a = new LinkedList();
    Node l_last = l.getHeadNode();
    Node m_first = m.getHeadNode();
    while(l_last != null) {
        a.insertLast(l_last.getElement());
        l_last = l_last.getNext();
    }
    while(m_first != null) {
        a.insertLast(m_first.getElement());
        m_first = m_first.getNext();
    }       
     return a;
}
于 2012-09-12T06:01:34.417 に答える