1. 문제 소개

3217. Delete Nodes From Linked List Present in Array

2. 나의 풀이법

head.val이 nums안에 들어가면 다음 값으로 바꾸는 방식으로 풀었다.
처음에는 if구문에서 리스트로 체크했을 때에는 시간초과가 되었지만, set으로 바꿔서 검사하니 시간초과가 되지 않았다.
또한 dummy를 쓰는 이유는 prev와 cur을 안정적으로 사용하기 위함이다.
시간복잡도는 $O(n + m)$이다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        ban = set(nums)
        dummy = ListNode(0)
        dummy.next = head
        prev, cur = dummy, head

        while cur:
            if cur.val in ban:
                prev.next = cur.next
            else:
                prev = cur
            cur = cur.next

        return dummy.next

3. 다른 풀이법

시간 복잡도는 똑같은 $O(n + m)$이지만, 풀이 방법은 다르다.
우선 남겨야하는 값들을 저장하고, 가존 노드의 val을 차례로 덮어 씌운다. 예를 들어 head → [1, 2, 6, 3, 4, 5, 6], nums = [6]일 때, 알고리즘을 통과한다면 vals = [1, 2, 3, 4, 5]이 남게 된다.
신기한 알고리즘이다.

class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        to_remove = set(nums)
        vals = []
        curr = head
        while curr:
            if curr.val not in to_remove:
                vals.append(curr.val)
            curr = curr.next

        if not vals:
            return None

        curr = head
        prev = None
        for v in vals:
            curr.val = v
            prev = curr
            curr = curr.next

        if prev:
            prev.next = None
        return head

4. 결론

처음 보는 알고리즘을 봐서 재미있었다.