Skip to content

← leetcode

Delete Nodes From Linked List Present in Array

· Medium

LeetCode problem 3217

My algorithm revolves around a two-pointer system. Basically, you keep track of one pointer, current, that initially points at head and a second pointer, consequent, that initially points to head->next. Then, you continue to iterate through the linked list with consequent:

  • if consequent is not a banned value inside of nums, then we want to include it in our modified list so we set current->next = consequent and then set current = current->next to not overwrite our past decisions
  • if consequent is a banned value inside of nums, then we just need to set consequent = consequent->next, as we will not be including the value inside our modified list once we run current->next = consequent.

We end up continuing this until we reach the end where consequent == nullptr, and can return our answer with head after setting current->next = nullptr since our consequent node has to be a nullptr (as that's why the while loop stopped).

code

/**
 * 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* modifiedList(vector<int>& nums, ListNode* head) {
        unordered_set<int> uniqueNums(nums.begin(), nums.end());
        while(uniqueNums.count(head->val)) {
            head = head->next;
        }

        ListNode *current = head, *consequent = head->next;

        while (consequent != nullptr) {
            if (!uniqueNums.count(consequent->val)) {
                current->next = consequent;
                current = current->next;
            }

            consequent = consequent->next;
        }
        current->next = nullptr;

        return head;
    }
};

complexity

  • Time: O(n) where n denotes the number of elements inside of head
  • Space: O(1)

time taken

  • 10 minutes and 52 seconds