문제

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]

풀이

• 중복이 들어오면 제거 -> 정렬이 되어있기 때문에 stack을 이용하면 좋다고 생각
• 스택의 마지막 값과 같음 = 중복 -> pop 그리고 stack의 마지막 노드의 연결을 끊음
• 연결을 끊지 않으면 1 2 2 와 같이 끝에서 중복이 나오면 1의 연결은 유지되었기 때문에 1의 next는 아직도 2임
• 또한 중복된 값을 저장 -> 1 1 1와 같이 홀수로 들어오면 1 1이 들어왔을 때 stack은 비어있고 또 들어오는 1이 중복인지 아닌지 알기 위해서는 중복이었던 값을 알아야함
• Leetcode는 Edge Case에 대한 것을 좀 조심해야할 듯

# 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]:
        
        #스택을 이용
        #스택의 마지막 값 == 현재 값 -> 중복 ->
        #스택의 마지막 값 != 현재 값 -> x 중복 -> 연결

        stack = []
        dup = -111

        node = head

        while node:
            if stack:
                if node.val == stack[-1].val:
                    stack.pop()
                    dup = node.val
                    if stack: stack[-1].next = None

                elif dup != node.val:
                    stack[-1].next = node
                    stack.append(node)
            else:
                if dup != node.val:
                    stack.append(node)

            node = node.next

        if stack: return stack[0]

        else: return None