Skip to main content
本文に 23 文字追加
ソース リンク
Avril
  • 117
  • 8

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記
共用部分の判定方法についてもアドバイスを頂けないでしょうか?

追記2
回答ありがとうございます。mergeを使用した場合O(nlogn)となってしまいますが、O(n)で実行できる方法はありますでしょうか?
追記3
merge方法自己解決しました。

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記
共用部分の判定方法についてもアドバイスを頂けないでしょうか?

追記2
回答ありがとうございます。mergeを使用した場合O(nlogn)となってしまいますが、O(n)で実行できる方法はありますでしょうか?

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記
共用部分の判定方法についてもアドバイスを頂けないでしょうか?

追記2
回答ありがとうございます。mergeを使用した場合O(nlogn)となってしまいますが、O(n)で実行できる方法はありますでしょうか?
追記3
merge方法自己解決しました。

本文に 76 文字追加
ソース リンク
Avril
  • 117
  • 8

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記
共用部分の判定方法についてもアドバイスを頂けないでしょうか?

追記2
回答ありがとうございます。mergeを使用した場合O(nlogn)となってしまいますが、O(n)で実行できる方法はありますでしょうか?

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記
共用部分の判定方法についてもアドバイスを頂けないでしょうか?

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記
共用部分の判定方法についてもアドバイスを頂けないでしょうか?

追記2
回答ありがとうございます。mergeを使用した場合O(nlogn)となってしまいますが、O(n)で実行できる方法はありますでしょうか?

本文に 39 文字追加
ソース リンク
Avril
  • 117
  • 8

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記
共用部分の判定方法についてもアドバイスを頂けないでしょうか?

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?

たとえば

-900->120->200->230
                   \
                    452->700
                   /
           -10->200

となっている連結リストなら

-900->-10->120->200->200->230->452->700

としたいです。
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記
共用部分の判定方法についてもアドバイスを頂けないでしょうか?

タイトルを編集
リンク
Avril
  • 117
  • 8
読み込んでいます
ソース リンク
Avril
  • 117
  • 8
読み込んでいます