LeetCode 203. リストから要素を削除

問題リンク：203. Remove Linked List Elements

以下の3つのポイントに注意する：

1. ヘッドノードが値を持つ場合、その値が削除対象と一致するか確認し、一致すればヘッドを更新する。
2. ノードを削除する際は、まず次のノードへのリンクを設定してから削除を行う。
3. メモリのオーバーフローを避ける。

以下のように、現在のノードの次のノードを指すポインタを使用することがあるが、現在ノードがNULLの場合、そのnextにアクセスするとエラーになる。

// ヘッドノードが削除対象の場合を先に処理
while (head != nullptr && head->val == val) {
    ListNode* temp = head;
    head = head->next;
    delete temp;
}
if (head == nullptr) return head; // リストが空かどうかを確認し、さもなければ初期化時にエラーが発生する

ListNode* current = head;
ListNode* nextNode = head->next;
while (current != nullptr && nextNode != nullptr) {
    if (nextNode->val == val) {
        ListNode* temp = nextNode;
        current->next = nextNode->next;
        nextNode = current->next;
        delete temp;
    } else {
        nextNode = nextNode->next;
        current = current->next;
    }
}
return head;

LeetCode 707. リストの設計

問題リンク：707. Design Linked List

1. クラスの実装は久しぶりだったので、構造体やコンストラクタの使い方に慣れていないことがあった。C++では、独自のコンストラクタを定義することで、ノードに値を直接割り当てられる。

public:
    struct ListNode {
        int value;
        ListNode* next;
        // リストノードの初期化
        ListNode(int value): value(value), next(nullptr) {}
    };

2. リストを定義する際、仮想のヘッドノードを使うと便利である。これにより空リストを保持でき、最初の要素の挿入や削除が容易になる。

MyLinkedList() {
    size = 0;
    dummyHead = new ListNode(0);
}

3. 要素の追加・削除時には、リストのサイズを適切に更新する必要がある。削除したノードを指すポインタはnullptrに設定し、ダングリングポインタにならないようにする（deleteされた後のポインタは不定な値を指すため、メモリリークの原因となる）。

4. ノードの挿入や削除は、対象位置の一つ前のノードに移動してから行うと簡単である。末尾に追加する際には、最後のノードのnextがnullptrになることを意識する。

class MyLinkedList {
public:
    struct ListNode {
        int value;
        ListNode* next;
        ListNode(int value): value(value), next(nullptr) {}
    };

    MyLinkedList() {
        size = 0;
        dummyHead = new ListNode(0);
    }

    int get(int index) {
        if (index < 0 || index >= size) return -1;
        ListNode* current = dummyHead->next;
        while (index--) {
            current = current->next;
        }
        return current->value;
    }

    void addAtHead(int value) {
        ListNode* newNode = new ListNode(value);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }

    void addAtTail(int value) {
        ListNode* newNode = new ListNode(value);
        ListNode* current = dummyHead;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
        newNode->next = nullptr;
        size++;
    }

    void addAtIndex(int index, int value) {
        if (index > size || index < 0) return;
        else if (index == size) {
            addAtTail(value);
        } else {
            ListNode* newNode = new ListNode(value);
            ListNode* current = dummyHead;
            while (index--) {
                current = current->next;
            }
            newNode->next = current->next;
            current->next = newNode;
            size++;
        }
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        else {
            ListNode* current = dummyHead;
            while (index--) {
                current = current->next;
            }
            ListNode* nodeToDelete = current->next;
            current->next = nodeToDelete->next;
            delete nodeToDelete;
            size--;
            nodeToDelete = nullptr; // ダングリングポインタを防ぐ
        }
    }

private:
    int size;
    ListNode* dummyHead;
};

LeetCode 206. リストの反転

問題リンク：206. Reverse Linked List

最初は複数のノード定義方法に惑わされてしまったが、実際には新しいノードを作成する必要はなく、既存のノードのポインタだけを変更すればよい。二つのポインタを使って操作する。curポインタを更新する前に、その次のノードを一時的に保存しておく必要がある。そうしないと、ポインタの変更後に次のノードにアクセスできなくなる。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return head;

        ListNode* prev = nullptr;
        ListNode* current = head;
        while (current) {
            ListNode* temp = current->next; // 次のノードを一時的に保存
            current->next = prev;
            prev = current;
            current = temp;
        }
        return prev;
    }
};

最近忙しくて再帰アルゴリズムの勉強ができていない。