LeetCode 82(Remove Duplicates from Sorted List II)

1. 문제 링크 

• https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/

Partition List - LeetCode

2. 문제 설명

• 정렬된 linked list인 head가 주어졌을 때, 중복된 숫자 노드를 전부 제외하여 반환. 
• 예시1) linked list가 [1,2,3,3,4,4,5]이면, 3과 4는 각 2번씩 중복되어 있으므로, 전부 제거하여 [1,2,5]의 linked list반환
• 예시2) linked list가 [1,1,1,2,3]이면, 1이 3번 중복되어 있으므로, [2,3] 반환

3. 처음 풀이

• 우선 가장 첫번째 node의 중복도 포함하기 위해서, 더미 ListNode (output)를 만들어 놓고, 
• fast, slow = output.next, output으로 설정해 둔 뒤, 
• fast와 fast.next가 None이 아닌 경우에 대해서 로직을 작성해두었다.
  • 만약 fast.val이 fast.next.val과 같다면 중복이 있다는 것이므로, fast를 계속 한 칸씩 옮겨주고, 
  • 그 값을 slow.next에 붙여주었다. → 이렇게 하면 중복된 Node는 아예 없어지게 된다.
  • fast.val과 fast.next.val이 같지 않다면, slow를 한 칸 이동 시키고, 
  • 공통적으로 fast를 한 칸 이동시켜준 뒤, 최종적으로 output.next (더미노드가 맨 앞에 있으므로)를 반환
• 이렇게 짜기까지 생각보다 여러번의 시행착오가 있었는데,
  • 자꾸 NoneType Error 가 발생했던 부분 (이는 fast, fast.next값이 있을 때 while 돌도록 해결)
  • slow.next에 필요없는 것을 건너뛰고 붙이는 부분이 헷갈렸었다.
• runtime같은 경우는 요새 leetcode가 평소랑 달리 계속 하위 5%, 99%가 같이 등장했다. 
• runtime 자체는 나쁘지 않았던 것으로 보인다. 

# 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]:

        output = ListNode(101)
        output.next = head
        fast, slow = output.next, output

        while fast and fast.next:
            
            if fast.val == fast.next.val:
                while fast.next and fast.val == fast.next.val:
                    fast = fast.next
                slow.next = fast.next
                
            else:
                slow = slow.next
            
            fast = fast.next

        return output.next

4. 다른 풀이

• 좋은 풀이인진 모르겠으나, 기존 노드에서 중복값들을 식별한 후, 중복된 값을 가진 노드를 새로운 리스트에서 제거하는 방식.
• 별도의 set을 구성하여, 중복과 중복되지 않은 값을 각각 분리하여 넣어 두고,
• 중복된 값을 새로운 연결리스트에서 제외
• 다른 접근이라 가져와봄.

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # 중복되지 않은 값들을 담기 위한 set
        unique_vals = set()
        duplicates = set()

        current = head
        # 중복되는 값 찾기
        while current:
            if current.val in unique_vals:
                duplicates.add(current.val)
            else:
                unique_vals.add(current.val)
            current = current.next

        # 중복된 값을 제외한 새로운 연결 리스트 생성
        dummy = ListNode(0)
        dummy.next = head
        prev, current = dummy, head

        while current:
            if current.val in duplicates:
                prev.next = current.next
            else:
                prev = current
            current = current.next

        return dummy.next

 

5. 배운 점 

• LinkedList를 쓸 때 NoneType 에러 안발생하게 잘 작성하자.