[Leetcode] 82. Remove Duplicates from Sorted List II

Solution 1. memoization

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        memo = {}
        newhead = ListNode(0)
        cur = newhead
        while head:
            if head.val not in memo:
                memo[head.val] = 1
                cur.next = ListNode(head.val)
                cur = cur.next
            else:
                memo[head.val] += 1
            head = head.next

        lst = [k for k, v in memo.items() if v == 1]
        newhead = ListNode(0)
        cur = newhead
        for i in lst:
            cur.next = ListNode(i)
            cur = cur.next

        return newhead.next

Solution 2. Two Pointer (플로이드 사이클 알고리즘 응용)

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        fast, slow = head, dummy

        # slow는 기록이 완료된 노드
        # fast는 탐색을 진행하는 노드 
        while fast:
            while fast.next and fast.val == fast.next.val:
                fast = fast.next
            if slow.next == fast:
                slow = slow.next
                fast = fast.next 
            else:
                slow.next = fast.next
                fast = fast.next

        return dummy.next