3217. Delete Nodes From Linked List Present in Array

Posted on Edited on In

3217. Delete Nodes From Linked List Present in Array

Description

You are given an array of integers nums and the head of a linked list. Return the head of the modified linked list after removing all nodes from the linked list that have a value that exists in nums.

Example 1:

1
2
3
Input: nums = [1,2,3], head = [1,2,3,4,5]

Output: [4,5]

Explanation:

Remove the nodes with values 1, 2, and 3.

Example 2:

1
2
3
Input: nums = [1], head = [1,2,1,2,1,2]

Output: [2,2,2]

Explanation:

Remove the nodes with value 1.

Example 3:

1
2
3
Input: nums = [5], head = [1,2,3,4]

Output: [1,2,3,4]

Explanation:

No node has value 5.

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • All elements in nums are unique.
  • The number of nodes in the given list is in the range [1, 10^5].
  • 1 <= Node.val <= 10^5
  • The input is generated such that there is at least one node in the linked list that has a value not present in nums.

Hints/Notes

Solution

Language: C++

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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) {
        set<int> s(nums.begin(), nums.end());
        ListNode dummy(0);
        ListNode* p = &dummy;
        while (head) {
            if (!s.contains(head->val)) {
                p->next = head;
                p = p->next;
            }
            head = head->next;
        }
        p->next = nullptr;
        return dummy.next;
    }
};

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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) {
        set<int> s(nums.begin(), nums.end());
        ListNode dummy(0);
        dummy.next = head;
        ListNode* tmp = &dummy;
        while (tmp->next) {
            if (s.contains(tmp->next->val)) {
                tmp->next = tmp->next->next;
            } else {
                tmp = tmp->next;
            }
        }
        return dummy.next;
    }
};