Leetcode - 203 リンクリストの要素削除

この問題のシンプルな解決法は、削除する要素の位置を判断し、2つの場合を分けることです。削除する要素が先頭であるか、そうでないかです。先頭削除の場合は、一時的なポインタを作成し、頭のポインタを更新します。非先頭削除の場合は、前後の要素を連結します。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 先頭要素の削除
        while (head != nullptr && head->val == val) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }
        // 非先頭要素の削除
        if (head == nullptr) return nullptr;
        ListNode* current = head;
        while (current->next != nullptr) {
            if (current->next->val == val) {
                ListNode* temp = current->next;
                current->next = current->next->next;
                delete temp;
            } else {
                current = current->next;
            }
        }
        return head;
    }
};

Leetcode - 707 リンクリストの設計

リンクリストの設計は、各操作を個別に実装する必要があります。この実装では、ダミーヘッドを使用し、サイズを追跡します。現在のバージョンでは、addAtTailとaddAtIndexメソッドにバグがあります。

class MyLinkedList {
public:
    struct LinkNode {
        int val;
        LinkNode* next;
        LinkNode(int val) : val(val), next(nullptr) {}
    };
    MyLinkedList() {
        dummyHead = new LinkNode(0);
        size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        LinkNode* current = dummyHead->next;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }
        return current->val;
    }
    
    void addAtHead(int val) {
        LinkNode* newNode = new LinkNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        LinkNode* current = dummyHead;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = new LinkNode(val);
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }
        LinkNode* current = dummyHead;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }
        LinkNode* newNode = new LinkNode(val);
        newNode->next = current->next;
        current->next = newNode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        LinkNode* current = dummyHead;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }
        if (current->next == nullptr) return;
        LinkNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
        size--;
    }
    
    void printLinkNode() {
        LinkNode* current = dummyHead->next;
        while (current != nullptr) {
            std::cout << current->val << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

private:
    int size;
    LinkNode* dummyHead;
};

Leetcode - 206 リンクリストの逆転

この問題の解決法は、双指針を用いて各要素のリンクを逆転させることです。この方法は非常にシンプルで、リンクリストの逆転を効率的に実現します。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return nullptr;
        ListNode* prev = nullptr;
        ListNode* current = head;
        while (current != nullptr) {
            ListNode* nextNode = current->next;
            current->next = prev;
            prev = current;
            current = nextNode;
        }
        return prev;
    }
};