82. Remove Duplicates from Sorted List II

Description

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

• Input: head = [1,2,3,3,4,4,5]
• Output: [1,2,5]

Example 2:

• Input: head = [1,1,1,2,3]
• Output: [2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Submitted Code

# 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]:
        dummy = ListNode(0, head)
        prev = dummy

        while head:
            if head.next and head.val == head.next.val:
                dup = head.val                  # 중복 숫자 기억
                while head and head.val == dup: # 중복 숫자 전부 스킵
                    head = head.next
                prev.next = head                # 연결 이어붙이기
            else:
                prev = head
                head = head.next

        return dummy.next

Runtime: 0 ms | Beats 100.00%
Memory: 19.31 MB | Beats 33.17%

83. Remove Duplicates from Sorted List 문제와 달리 중복값 자체를 전부 제거해야 해서 조금 더 까다로워졌다. dummy 노드가 거의 필수로 사용되며, 이전 정상 노드(prev)를 유지하는 것이 중요하다.

Other Solutions

1st

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        cur = head

        while cur and cur.next:
            if cur.val == cur.next.val:
                while cur.next and cur.val == cur.next.val:
                    cur = cur.next
                prev.next = cur.next  # Skip all duplicates
            else:
                prev = prev.next  # Move to next distinct node
            cur = cur.next

        return dummy.next

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

중복 숫자를 굳이 기억하지 않아도 된다.