Reversed LinkedList

Intro

単一リンクリスト（Singly Linked List）は、各ノードがデータと次のノードへの参照（ポインタ）を持つ線形データ構造です。 この構造は、動的にサイズを調整でき、要素の挿入や削除が容易であるという利点があります。

単一リンクリストの構造:

• ノード（Node）: 各ノードは以下の2つの部分で構成されます。
  1. データ（Data）: ノードが保持する値。
  2. 次への参照（Next）: 次のノードを指すポインタ。

リストの開始点は「ヘッド（Head）」と呼ばれ、リストの終端は次のノードが存在しないことで示されます。

部分反転（Reverse）操作:

単一リンクリスト内の特定の区間のノードを反転させる操作は、以下の手順で行われます。

1. ダミーノードの作成: ヘッドの前にダミーノードを追加し、境界条件を簡単に処理できるようにします。
2. ポインタの設定: 反転区間の開始位置まで移動するためのポインタを設定します。
3. 部分リストの反転: 設定したポインタを用いて、指定された区間のノードを反転させます。
4. リストの再接続: 反転された部分リストを元のリストと再接続します。

この操作により、リストの特定の区間を効率的に反転させることができます。

例として、以下のコードは単一リンクリスト内の指定された区間 [left, right] のノードを反転させる機能を実装しています。

/**
 * 単一リンクリストのノードの定義
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 例外処理: headがnull、またはleftとrightが同じ場合
        if (head == null || left == right) {
            return head;
        }

        // ダミーノードの作成
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        // leftの前までprevを移動
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }

        // 反転開始ノードとその次のノードを設定
        ListNode start = prev.next;
        ListNode then = start.next;

        // 部分リストの反転
        for (int i = 0; i < right - left; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }

        return dummy.next;
    }
}

このコードは、単一リンクリスト内の指定された区間 [left, right] のノードを反転させる機能を実装しています。 ダミーノードを使用して境界条件を処理し、ポインタ操作を通じて部分リストを効率的に反転させます。