algorithm - リンクリストを逆にしてマージする

Question

問題：ソートされたリンクリストが与えられた

1->2->3->4->5->6->7

リンクリスト内のポインタを変更して作成します

7->1->6->2->5->3->4

一定のスペースを使用します。

私は次のアルゴリズムを使用してそれを解決しようとしました：

1. 高速ノードと低速ノードの2つのノードを使用して、リンクリストの中間ノードを見つけます。

2. リンクリストを中間ノードから逆にします。中央のノードをyとしてマークし、開始ノードをxとしてマークします。

   1->2->3->7->6->5->4
   x        y
   

3. y =中間ノードかつy！= x.nextの場合、yとx.nextを交換します。次に、xとx.nextを交換します。

   1->7->3->2->6->5->4
   x        y
   7->1->3->2->6->5->4
   x        y
   

   xを2ノード進め、yを1ノード進めます。

   7->1->3->2->6->5->4
         x     y     
   

4. ここで、if（x！= y）{xとyを入れ替える}

   7->1->6->2->3->5->4
         x     y
   

5. xを2ノード進め、yを1ノード進めます

   7->1->3->2->6->5->4
               x  y
   

6. yがnullになる（リンクリストの最後に到達する）か、x == yになるまで、手順4と5を繰り返します。

だから最終的に私たちは得る

7->1->6->2->5->3->4

質問：

これを行うためのより簡単な方法はありますか？

Answer 1

これは簡単な解決策です：

1. リストのサイズが見つかりました。
2. 2 つの同じリストにこぼれました。
3. 2番目の部分を逆にします。
4. リストをマージします。

サンプル：

1. 1->2->3->4->5->6->7 サイズは7。(4 と 3 で割る必要があります)
2. 1->2->3->4とで割る5->6->7
3. 2 番目の部分を反転1->2->3->4し、7->6->5
4. マージ：7->1->6->2->5->3->4

Answer 2

リンクされたリストの問題の問題 17 と 18には、2 つの洗練された解決策があります。