Insertion Sort of Single LinkedList

挿入ソートアルゴリズムの手順:

1. 初期状態: リストの最初の要素のみを含む部分的にソートされたリストを用意します。
2. 反復処理: 未ソートの入力データから1つの要素を取り出し、ソート済みリスト内の適切な位置に挿入します。
3. 終了条件: 未ソートの入力要素がなくなるまでこのプロセスを繰り返します。

単一リンクリストにおける挿入ソートの実装:

単一リンクリストで挿入ソートを実装するには、以下の手順を踏みます:

1. ダミーノードの作成: ソート済みリストの開始を示すダミーノードを作成します。
2. 現在のノードの探索: 元のリストの各ノードを順に処理します。
3. 挿入位置の探索: ソート済みリスト内で現在のノードの値を挿入する適切な位置を見つけます。
4. ノードの挿入: 現在のノードをソート済みリストの適切な位置に挿入します。
5. 次のノードへの移動: 元のリストの次のノードに移動し、プロセスを繰り返します。

Example

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode curNode = head;
        if (curNode.next == null) return head;

        while (curNode != null) {
            ListNode nextNode = curNode.next;
            int curr = curNode.val;
            while (nextNode != null) {
                if (curr > nextNode.val) {
                    int tmp = curr;
                    curNode.val = nextNode.val;
                    curr = curNode.val;
                    nextNode.val = tmp;
                }
                nextNode = nextNode.next;
            }
            curNode = curNode.next;
        }

        return head;
    }
}

コードの説明:

• 初期設定: curNodeをリストの先頭ノードheadに設定します。
• リストの走査: curNodeがnullでない限り、以下の処理を繰り返します:
  • 次のノードの設定: nextNodeをcurNodeの次のノードに設定します。
  • 現在の値の保存: currにcurNodeの値を保存します。
  • 内部ループ: nextNodeがnullでない限り、以下の処理を繰り返します:
    • 値の比較と交換: currがnextNodeの値より大きい場合、値を交換します。
    • 次のノードへの移動: nextNodeをその次のノードに更新します。
  • curNodeの更新: curNodeをその次のノードに更新します。
• ソート済みリストの返却: headを返します。