問題

この問題では、リンクリストの先頭ノード head と整数 val が与えられます。リンクリストから Node.val == val を満たす全てのノードを削除し、新しい先頭ノードを返します。

例1:

入力: head = [1,2,6,3,4,5,6], val = 6
出力: [1,2,3,4,5]

例2:

入力: head = [], val = 1
出力: []

例3:

入力: head = [7,7,7,7], val = 7
出力: []

制約:

• リスト内のノード数は [0, 104] の範囲内
• 1 <= Node.val <= 50
• 0 <= val <= 50

解法1: 仮想ヘッドノードを使用しない場合

コード

// シングルリンクリストの定義
struct ListNode {
    int value;
    ListNode* next;
    ListNode() : value(0), next(nullptr) {}
    ListNode(int x) : value(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : value(x), next(next) {}
};

class ListModifier {
public:
    ListNode* removeElements(ListNode* head, int target) {
        // 先頭ノードが存在し、その値が target と等しい場合
        while (head != nullptr && head->value == target) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
            temp = nullptr;
        }

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

複雑さ分析

• 時間計算量: O(n)
• 空間計算量: O(1)

解法2: 仮想ヘッドノードを使用する場合

コード

// シングルリンクリストの定義
struct ListNode {
    int value;
    ListNode* next;
    ListNode() : value(0), next(nullptr) {}
    ListNode(int x) : value(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : value(x), next(next) {}
};

class ListModifier {
public:
    ListNode* removeElements(ListNode* head, int target) {
        if (!head) {
            return nullptr;
        }

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* current = dummyHead;

        while (current->next != nullptr) {
            if (current->next->value == target) {
                ListNode* temp = current->next;
                current->next = current->next->next;
                delete temp;
                temp = nullptr;
            } else {
                current = current->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        dummyHead = nullptr;
        return head;
    }
};

複雑さ分析

• 時間計算量: O(n)
• 空間計算量: O(1)