알고리즘
[LeetCode] 83. Remove Duplicates from Sorted List
이준언
2024. 9. 14. 18:13
안녕하세요!
오늘은 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
다음과 같은 런타임을 얻었습니다.
더 좋은 풀이법이 있다면 알려주시면 감사하겠습니닷!