LeetCode [83]: Remove Duplicates from Sorted List

📌 LeetCode [83]: Remove Duplicates from Sorted List

🔗 문제 링크

---

문제 설명 📄

주어진 정렬된 단일 연결 리스트에서 연속된 중복 노드를 제거하고, 각 값이 하나씩만 나타나는 연결 리스트를 반환하는 문제입니다.

예제 입력/출력

• 입력: head = [1, 1, 2]
  출력: [1, 2]
• 입력: head = [1, 1, 2, 3, 3]
  출력: [1, 2, 3]

제약 조건

• 노드의 개수는 0 <= n <= 300입니다.
• 리스트의 값은 -100 <= Node.val <= 100이며, 정렬된 상태로 주어집니다.

---

문제 접근 방식 📋

1. 정렬된 리스트의 특성 활용:
   • 리스트가 정렬되어 있으므로, 현재 노드와 다음 노드의 값만 비교하면 중복 여부를 알 수 있습니다.
2. 연속된 중복 노드 제거:
   • 현재 노드와 다음 노드의 값이 같으면, 현재 노드의 next를 수정하여 중복 노드를 건너뜁니다.
3. 현재 노드를 이동:
   • 값이 같지 않을 경우, 다음 노드로 이동하며 반복합니다.

---

Solution 💻

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head: 
            return head

        current = head
        while current and current.next:
            if current.val == current.next.val:
                current.next = current.next.next
            else:
                current = current.next

        return head

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(n))
  • 리스트의 모든 노드를 한 번씩 순회합니다.
• 공간 복잡도: (O(1))
  • 추가 공간 없이 원본 리스트를 수정합니다.

---