C++로 정렬된 연결 리스트에서 중복 요소 제거하기

문제 개요

정렬된 연결 리스트(Linked List)가 주어졌을 때, 모든 중복 요소를 제거하여 각 값이 한 번만 나타나도록 만들어야 합니다.

예를 들어 입력이 [1,1,2,3,3,3,4,5,5]라면, 출력은 [1,2,3,4,5]가 됩니다.

접근 방법

리스트가 이미 정렬되어 있으므로, 서로 인접한 노드끼리만 비교하면 중복을 쉽게 찾을 수 있습니다. 이때 더미(dummy) 노드를 활용하면 헤드 노드 처리 로직을 단순화할 수 있습니다. 알고리즘의 진행 순서는 다음과 같습니다.

• 값이 INT_MIN인 더미 노드를 생성하고, 그 next를 head에 연결합니다.
• curr 포인터를 더미 노드로 초기화합니다.
• curr가 NULL이 아닌 동안 아래 과정을 반복합니다.
  • next를 curr의 다음 노드로 설정합니다.
  • next가 NULL이 아니고 next의 값이 curr의 값과 같다면, next를 계속 앞으로 이동시켜 중복 구간을 건너뜁니다.
  • curr->next를 next에 연결하여 중복 노드들을 리스트에서 제거합니다.
  • curr를 next 위치로 이동시킵니다.
• 모든 반복이 끝나면 더미 노드의 next를 결과로 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
      int val;
      ListNode *next;
      ListNode(int data){
         val = data;
         next = NULL;
      }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
void print_list(ListNode *head){
   ListNode *ptr = head;
   cout << "[";
   while(ptr){
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
public:
   ListNode* deleteDuplicates(ListNode* head) {
      ListNode*dummy = new ListNode(INT_MIN);
      dummy->next = head;
      ListNode * curr = dummy;
      while(curr){
         ListNode * next = curr->next;
         while(next && next->val==curr->val)
            next = next->next;
         curr->next = next;
         curr=next;
      }
      return dummy->next;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,2,3,3,3,4,5,5};
   ListNode *head = make_list(v);
   print_list(ob.deleteDuplicates(head));
}

입력

{1,1,2,3,3,3,4,5,5}

출력

[1, 2, 3, 4, 5]

복잡도 분석

이 알고리즘은 각 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 또한 포인터 몇 개만 추가로 사용하고 별도의 자료구조가 필요하지 않기 때문에 공간 복잡도는 O(1)입니다.