本日の課題

• LeetCode 203. リンクリスト要素の削除
• LeetCode 707. リンクリストの設計
• LeetCode 206. リンクリストの反転

基本概念の整理

ノードの追加処理では、新しいノード（current.next）を先に処理し、古いノード（previous.next）を後から処理します。

ノードの削除では、現在のノードを削除するには、その前のノードを知る必要があります。そのため、currentとpreviousの2つのポインタを使用します。

ダミーヘッドノードの使用は非常に重要です。

203. リンクリスト要素の削除

アプローチ

リンクリストの削除操作において、現在のノードを削除するにはその前のノードを知る必要があります。そのため、currentとpreviousの2つのポインタを使用します。

解答例

/**
 * 単一リンクリストの定義
 */
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 removeElements(ListNode head, int val) {
        if (head == null) return head;
        
        // ダミーノードを作成して境界条件を簡略化
        ListNode dummyNode = new ListNode(-1, head);
        ListNode previous = dummyNode;
        ListNode current = head;
        
        while (current != null) {
            if (current.val == val) {
                // 削除対象のノードをスキップ
                previous.next = current.next;
            } else {
                // 削除しない場合はpreviousを更新
                previous = current;
            }
            current = current.next;
        }
        
        return dummyNode.next;
    }
}

707. リンクリストの設計

アプローチ

リンクリストは配列とは異なり、要素を一つずつたどる必要があります。特に特殊な位置（先頭、末尾、中間）の処理に注意が必要です。

解答例

class MyLinkedList {
    private int length;
    private ListNode firstNode;

    public MyLinkedList() {
        length = 0;
        firstNode = new ListNode(0);        
    }
    
    public int get(int index) {
        if (index < 0 || index >= length) {
            return -1;
        }
        
        ListNode currentNode = firstNode;
        // 指定された位置まで移動
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(length, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index > length) {
            return;
        }
        
        if (index < 0) {
            index = 0;
        }
        
        length++;
        ListNode predecessor = firstNode;
        // 挿入位置の一つ手前に移動
        for (int i = 0; i < index; i++) {
            predecessor = predecessor.next;
        }

        ListNode newNode = new ListNode(val);
        // 新しいノードを挿入
        newNode.next = predecessor.next;
        predecessor.next = newNode;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= length) {
            return;
        }
        
        length--;
        if (index == 0) {
            // 先頭ノードを削除
            firstNode = firstNode.next;
            return;
        }
        
        ListNode predecessor = firstNode;
        // 削除位置の一つ手前に移動
        for (int i = 0; i < index; i++) {
            predecessor = predecessor.next;
        }
        // ノードを削除
        predecessor.next = predecessor.next.next;
    }
}

/**
 * MyLinkedListオブジェクトは以下のようにインスタンス化して使用します:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index, val);
 * obj.deleteAtIndex(index);
 */

206. リンクリストの反転

アプローチ

最初にダブルポインタを思いつきましたが、すぐには解決策が見つかりませんでした。リンクリストの順序を逆にする方法を考えれば、一時的なノードを使用してポインタの方向を反転させることで解決できます。現在のノードの次のポインタを一時的に保存することが重要です。

解答例

/**
 * 単一リンクリストの定義
 */
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 reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        ListNode nextTemp = null;

        while (current != null) {
            // 次のノードを一時保存
            nextTemp = current.next;
            // 現在のノードの向きを逆転
            current.next = previous;
            // ポインタを進める
            previous = current;
            current = nextTemp;
        }
        // 反転後の新しいヘッドを返す
        return previous;
    }
}