darkan

// 単方向リンクリスト
struct ListNode {
    int val;  // ノードに保存される要素
    ListNode *next;  // 次のノードを指すポインタ
    ListNode(int x) : val(x), next(NULL) {}  // ノードのコンストラクタ
};

ListNode* head = new ListNode(5);

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 仮のヘッドノードを設定
        dummyHead->next = head; // 仮のヘッドノードをheadに指すようにし、削除操作を行いやすくする
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

class MyLinkedList {
public:
    // リンクリストノードの構造体を定義
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // リンクリストを初期化
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // ここで定義されたヘッドノードは仮のヘッドノードであり、実際のリンクリストのヘッドノードではない
        _size = 0;
    }

    // index番目のノードの値を取得する。indexが不正な値の場合は-1を返す。注意：indexは0から始まる。0番目のノードはヘッドノード。
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // --indexを使用すると無限ループに陥る
            cur = cur->next;
        }
        return cur->val;
    }

    // リンクリストの最前面にノードを挿入する。挿入後、新しく挿入されたノードがリンクリストの新しいヘッドノードとなる。
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    // リンクリストの最後にノードを追加する
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    // index番目のノードの前に新しいノードを挿入する。例えば、indexが0の場合、新しく挿入されたノードがリンクリストの新しいヘッドノードとなる。
    // indexがリンクリストの長さと等しい場合、新しく挿入されたノードがリンクリストの尾ノードとなる。
    // indexがリンクリストの長さを超える場合は空を返す。
    // indexが0未満の場合はヘッドにノードを挿入する。
    void addAtIndex(int index, int val) {

        if(index > _size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // index番目のノードを削除する。indexがリンクリストの長さ以上の場合は直接return。注意：indexは0から始まる。
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        // delete命令はtmpポインタが元々指していたメモリ部分を解放したことを示す。
        // deleteされた後のポインタtmpの値（アドレス）はNULLではなく、ランダムな値である。つまり、deleteされた後、
        // もしtmp=nullptrを追加しないと、tmpは無効なポインタになる。
        // その後のプログラムで不注意にtmpを使用すると、予測できないメモリ空間を指すことになる。
        tmp=nullptr;
        _size--;
    }

    // リンクリストを印刷する
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // curの次のノードを保存
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // curの次のノードを保存する。次にcur->nextを変更するため。
            cur->next = pre; // 反転操作
            // preとcurポインタを更新
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 二指針法のコードと比較できる。以下の再帰の書き方は、実際にはこの二つのステップを行っている。
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 二指針法の初期化と同じロジック
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};