Delete Nodes From Linked List Present in Array

Leetcode Problem:

• Delete Nodes From Linked List Present in Array

Summary

• Given an array of integers and the head of a linked list, return the head of the modified linked list after removing nodes with values that exist in the array.

Approach

• Use a set to store the values in the array, then traverse the linked list and create a new linked list with only the nodes that have values not in the set.

Complexity

• O(n + m) where n is the number of nodes in the linked list and m is the number of elements in the array

Explain

• The solution works by first creating a set of the values in the array
• Then it traverses the linked list, checking if each node's value is in the set
• If it is, the node is skipped
• If not, a new node is created with the same value and it becomes the head of the modified linked list
• This process continues until all nodes have been traversed.

Solution 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:
    set s;
    ListNode* ans;
    void traversal(ListNode* head){
        if (head == nullptr) return;
        traversal(head->next);
        if( s.find(head->val) != s.end()) return;

        ListNode* temp = new ListNode(head->val, ans);
        ans = temp;
    }
    ListNode* modifiedList(vector& nums, ListNode* head) {
        for(int i = 0 ; i < nums.size(); i++){
            s.insert(nums[i]);
        }
        traversal(head);
        return ans;    
    }
};