[LeetCode] Remove Duplicates from Sorted List II

82.Remove Duplicates from Sorted List II

각 노드가 나오는 갯수와, 각 노드를 dictionary 에 넣은 뒤에 key 값을 사용하여 비교하는 방법이다.
하지만, dictionary 는 파이썬에서는 key 가 들어간 순서가 보장되긴 하지만, 원래는 순서가 보장되지 않는 자료구조이기때문에, 이와같이 링크드 리스트에 사용하기에는 어울리지 않는다.
time O(2 * N)
space O(2 * N)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:

        nodeDic = dict()
        cntDic = dict()

        curr = head

        while (curr):
            cntDic[curr.val] = cntDic.get(curr.val, 0) + 1

            if (curr.val not in nodeDic):
                nodeDic[curr.val] = curr
            curr = curr.next

        start = None
        link = None

        for key in cntDic:
            if cntDic[key] == 1:
                if (start == None):
                    link = nodeDic[key]
                    start = nodeDic[key]
                else:
                    link.next = nodeDic[key]
                    link = nodeDic[key]
            else:
                continue

        if (link and link.next):
            link.next = None
        return start     

그럼 다른 방법은 뭐가 있을까 ?
바로 반복문을 활용해 연결하는 방법이다.
사실 이 방법은 항상 헷갈린다.
그래서 마지막 노드와 처음 노드에 대한 예외처리를 잘 해주어야한다.
time O(N)
space O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = ListNode(0)
        r = pre
        r.next = head

        curr = head
        while (curr and curr.next):
            if (curr.val != curr.next.val):
                pre.next = curr
                pre = curr
                curr = curr.next

            else:
                while (curr.next and curr.val == curr.next.val):
                    curr = curr.next
                curr = curr.next



        return r.next