Notice
250x250
Recent Posts
Recent Comments
Link
넘치게 채우기
[LeetCode] 3217. Delete Nodes From Linked List Present in Array 본문
PS/LeetCode
[LeetCode] 3217. Delete Nodes From Linked List Present in Array
riveroverflow 2024. 9. 6. 10:15728x90
반응형
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
}
728x90
반응형
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 725. Split Linked List in Parts (0) | 2024.09.08 |
---|---|
[LeetCode] 1367. Linked List in Binary Tree (0) | 2024.09.07 |
[LeetCode] 2028. Find Missing Observations (0) | 2024.09.05 |
[LeetCode] 874. Walking Robot Simulation (0) | 2024.09.04 |
[LeetCode] 1945. Sum of Digits of String After Convert (0) | 2024.09.03 |