特定値ノードの安全な削除（LeetCode 203）

連結リストから指定した整数と一致するノードを除去する処理では、先頭ノードと中間以降のノードで削除ロジックが異なる点に注意が必要です。先頭を削除する場合は参照そのものを更新する必要がありますが、中間ノードの削除は直前のノードの next ポインタを書き換えるだけで済みます。これらを無理に単一のループで統合しようとすると、条件分岐が複雑化しヌルポインタ例外の原因となります。

実装の複雑さを回避する最も確実な手法は、ダミーノード（仮想先頭ノード）を導入することです。ダミーノードを配置することで、実際の先頭ノードも含めて「直前のノードが存在する」という統一された前提で処理が可能になり、コードの分岐が大幅に削減されます。

public class LinkedListProcessor {
    public static ListNode removeElements(ListNode head, int targetValue) {
        if (head == null) return null;

        // 仮想ノードを配置して処理を統一
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode iterator = sentinel;

        while (iterator.next != null) {
            if (iterator.next.val == targetValue) {
                // 対象ノードをスキップ（リンクの繋ぎ替え）
                iterator.next = iterator.next.next;
            } else {
                // 削除対象でない場合はポインタを前進
                iterator = iterator.next;
            }
        }
        return sentinel.next;
    }
}

連結リストデータ構造の実装（LeetCode 707）

インデックスベースの操作（取得・挿入・削除）をサポートする連結リストを設計する際、要素数の追跡と境界値チェックが不可欠です。ダミーノードを採用すると、addAtHead や addAtIndex(0, val) などの特殊ケースを個別に実装する必要がなくなります。

位置指定の操作では、目的のインデックスにあるノード自体ではなく、その直前のノードまでトラバースする点が設計の核心です。インデックス 0 の操作にはダミーノードが直前のノードとして機能するため、全操作で同一の移動ロジックを適用できます。メソッド間のコード重複を防ぐため、共通のトラバース処理を内部メソッドに集約する構成が保守性に優れます。

public class SinglyLinkedList {
    private int nodeCount;
    private final ListNode virtualHead;

    public SinglyLinkedList() {
        this.nodeCount = 0;
        this.virtualHead = new ListNode(0);
    }

    public int get(int index) {
        if (index < 0 || index >= nodeCount) return -1;
        ListNode current = fetchPredecessor(index).next;
        return current.val;
    }

    public void addAtHead(int val) {
        insertAtIndex(0, val);
    }

    public void addAtTail(int val) {
        insertAtIndex(nodeCount, val);
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > nodeCount) return;
        insertAtIndex(index, val);
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= nodeCount) return;
        ListNode prevNode = fetchPredecessor(index);
        prevNode.next = prevNode.next.next;
        nodeCount--;
    }

    // 指定インデックスの直前ノードを取得する共通ロジック
    private ListNode fetchPredecessor(int targetIndex) {
        ListNode walker = virtualHead;
        for (int step = 0; step < targetIndex; step++) {
            walker = walker.next;
        }
        return walker;
    }

    private void insertAtIndex(int index, int value) {
        ListNode predecessor = fetchPredecessor(index);
        ListNode freshNode = new ListNode(value);
        freshNode.next = predecessor.next;
        predecessor.next = freshNode;
        nodeCount++;
    }
}

イテレーティブな連結リスト反転（LeetCode 206）

リストの向きを反転させる際、再帰ではなく反復手法を用いることでスタックオーバーフローのリスクを回避し、空間計算量を O(1) に抑えられます。標準的なアプローチは三つのポインタ変数を活用する手法です。

処理中は現在処理中のノード、その一つ前のノード、そして次のノードへの参照を一時的に保持する必要があります。ループ内では必ず次のノードを先にキャッシュし、現在のノードのポインタを前向きに変更してから、各ポインタを一つずつ前進させます。この順序を誤るとリンクが切断され、残りのノードにアクセスできなくなります。ループ終了時、反転処理が完了したリストの先頭は最後に処理されたノード（previous）が保持しているため、これを返す必要があります。

public class ListReverser {
    public static ListNode reverseList(ListNode root) {
        ListNode previousNode = null;
        ListNode currentNode = root;

        while (currentNode != null) {
            ListNode nextTemp = currentNode.next; // 次の位置をキャッシュ
            currentNode.next = previousNode;      // 連結方向を反転
            previousNode = currentNode;           // 前の位置ポインタを更新
            currentNode = nextTemp;               // 現在位置ポインタを前進
        }
        return previousNode; // 反転後の新しい先頭を返却
    }
}