[LeetCode] 3217. Delete Nodes From Linked List Present in Array

https://leetcode.com/problems/delete-nodes-from-linked-list-present-in-array/description/?envType=daily-question&envId=2024-09-06

leetcode - Delete Nodes From Linked List Present in Array

문제 유형 : 연결 리스트

문제 난이도 : Medium

 

문제

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.

 

정수 배열 nums와 연결리스트의 head가 주어진다.

nums에 있는 모든 수를 제거한 변형된 연결리스트를 반환하시오.

 

풀이

1. 앞부분 trimming

맨 앞의 노드가 nums의 요소인동안, head는 다음으로 건너뛴다.

그 뒤, head가 null이면 널포인터를 반환한다.

 

2. head뒤부터 중간 노드들 없애기

curr = head부터 시작한다.

curr과 curr의 다음 노드가 null인동안, 다음을 반복한다:

만약 curr의 다음노드가 nums의 요소라면, curr의 다음노드를 curr의 다음의 다음노드로 변경한다.

그렇지 않으면, curr는 다음노드로 넘어간다.

 

3. 맨 뒤 trimming

만약 curr이 null이 아니라면, curr의 다음을 null로 바꾼다.

 

1,2,3 이후, head를 반환한다.

 

코드

C++

/**
 * 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) {}
 * };
 */

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        set<int> s(nums.begin(), nums.end());
        while (head != nullptr && s.find(head->val) != s.end()) {
            head = head->next;
        }

        if (head == nullptr) {
            return nullptr;
        }
        ListNode* curr = head;

        while (curr != nullptr && curr->next != nullptr) {
            if (s.find(curr->next->val) != s.end()) {
                curr->next = curr->next->next;
            } else {
                curr = curr->next;
            }
        }

        return head;
    }
};

 

GO

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func modifiedList(nums []int, head *ListNode) *ListNode {
    m := make(map[int]bool)
    for _, v := range nums {
        m[v] = true
    }

    for head != nil && m[head.Val] {
        head = head.Next
    }

    if head == nil {
        return nil
    }

    curr := head
    for curr != nil && curr.Next != nil {
        if m[curr.Next.Val] {
            curr.Next = curr.Next.Next
        } else {
            curr = curr.Next
        }
    }

    if curr != nil {
        curr.Next = nil
    }

    return head
}