-1

私は、Javaですでにソートされている2つのリンクリストをマージするコードを開発しました。

次のことについてサポートが必要です。

  1. tempNodeを使用せずにマージされたリストのヘッドノードの値を保持するにはどうすればよいですか？

  2. このコードをより適切に最適化できますか？

    public static ListNode mergeSortedListIteration(ListNode nodeA, ListNode nodeB) {
   ListNode mergedNode ;
   ListNode tempNode ;      

if (nodeA == null) {
    return nodeB;
  } 
  if (nodeB == null) {
    return nodeA;
  }     


if ( nodeA.getValue() < nodeB.getValue())
{
    mergedNode = nodeA;
    nodeA = nodeA.getNext();
}
else
{
    mergedNode = nodeB;
    nodeB = nodeB.getNext();
}

tempNode = mergedNode; 

while (nodeA != null && nodeB != null)
{           

    if ( nodeA.getValue() < nodeB.getValue())
    {               
        mergedNode.setNext(nodeA);
        nodeA = nodeA.getNext();
    }
    else
    {
        mergedNode.setNext(nodeB);
        nodeB = nodeB.getNext();                
    }       
    mergedNode = mergedNode.getNext();
}

if (nodeA != null)
{
    mergedNode.setNext(nodeA);
}

if (nodeB != null)
{
    mergedNode.setNext(nodeB);
}       
return tempNode;
}
4

2 に答える 2

2

1：最初のノードの記録を保持する必要があります。つまり、それをなどの変数に格納する必要がありますtempNode。

2：いいえ。ここで最適化することはあまりありません。プロセスは非常に簡単です。

于 2012-07-24T14:28:16.613 に答える
2

いくつかの可能性があります：

mergedNode1）を使用して前のノードを追跡する代わりに、とを使用nodeA.getNext().getValue()しnodeB.getNext().getValue()ます。アルゴリズムはより複雑になり、いくつかのエッジケースを処理する必要がありますが、変数の1つを削除することは可能です。

2）二重リンクリストを使用してから、の代わりにとのnodeA.getPrev().getValue()いずれかを使用します。ここでもエッジケースに対処する必要があります。nodeB.getPrev().getValue()mergedNode

エッジケースに対処するには、、、またはを呼び出す前に参照ができないことを保証する必要があります。nullそうしないと、例外がスローされます。getPrev()getNext()getValue()

上記の変更により、変数を削除するために実行時間がわずかに犠牲になり、（さらに重要なことに）単純になることに注意してください。利益はわずかであり、開発者の時間は、操作を1〜2マイクロ秒短縮するよりもはるかに重要です。

于 2012-07-24T14:30:11.803 に答える