java - これは複数のリンクされたリストを並べ替える効率的な方法ですか?

Question

n 個の並べ替えられたリンク リストがあり、それぞれのサイズは n です。リンクされたリストの参照は、配列に格納されます。n 個の連結リストを単一のソート済み連結リストにマージする効率的なアルゴリズムは何ですか?

それらはすべてソートされているため：

1. ループを組み込む
2. 並べ替えられたすべてのリンク リストの最初のノードを確認し、それらを比較して並べ替えます。
3. 次のノードに進み、nullヒットするまで繰り返します。

これはこれを行う最も効率的な方法ですか？

Answer 1

それらをすべてリンクして（または単一のリストにダンプして）、一般的な並べ替えを使用するだけです。これにより、 nlog(n) パフォーマンスが得られます。あなたのやり方は n^2 です。