[LeetCode] 83. Remove Duplicates from Sorted List

안녕하세요!

 

오늘은 83. Remove Duplicates from Sorted List 문제를 풀어보겠습니다.

 

 

head는 이미 정렬된 linked list이고 head의 원소 중 중복된 원소가 없게 만드는 문제입니다.

 

제가 생각한 방법은 원소와 바로 다음 원소를 비교하며 같을 시 삭제해나가는 방법입니다.

 

사실 중복 제거를 보자마자 집합을 사용하는 방법을 먼저 떠올렸었는데요. 하지만 이 문제에서 head는 linked list이기 때문에 집합을 이용해 중복을 제거하기 위해서는 반복문을 통해 각 원소를 하나씩 순회하여 집합을 만들고 이를 다시 리스트로 만들어야하는데, 이 방법이 더 복잡하다고 합니다.

 

작성한 코드는 다음과 같습니다.

# Definition for singly-linked list.
# 연결 리스트를 정의
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # i는 head의 원소
        i = head

        # i와 다음 원소가 존재할 때만 반복
        while i and i.next:
            # 원소 i가 다음 원소와 같다면 그 다음 원소로 건너뛰기
            if i.val == i.next.val:
                i.next = i.next.next

            else:
                i = i.next
        # 중복을 제거한 linked list 출력
        return head

 

다음과 같은 런타임을 얻었습니다.

 

더 좋은 풀이법이 있다면 알려주시면 감사하겠습니닷!