정렬된 연결 리스트가 주어졌을 때, 두 번 이상 등장한 모든 요소를 제거하여 고유한(distinct) 요소만 남기는 것이 이 문제의 목표입니다. 예를 들어 입력 리스트가 [1,1,1,2,2,3,5,6,6,7,8]이라면, 1·2·6은 각각 여러 번 나타나므로 모두 제거되고 최종 결과는 [3,5,7,8]이 됩니다.
이 문제는 더미(dummy) 노드를 활용해 결과 리스트를 새로 구성하는 방식으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 현재 노드와 다음 노드의 값을 비교하여, 중복 구간 전체를 한 번에 건너뛰고 고유한 값만 결과 리스트에 연결하는 것입니다.
알고리즘 단계
- 값이 -1인 더미 노드를 생성하고, prev := NULL, dummyPtr := dummy로 초기화합니다.
- head가 null이 아닌 동안 다음 과정을 반복합니다.
- head의 다음 노드가 없거나, head의 값이 다음 노드의 값과 다른 경우 (고유한 값): dummyPtr의 next를 head에 연결한 뒤, 임시 변수 temp에 head의 next를 저장하고 head의 next를 null로 만듭니다. 이후 head := temp, dummyPtr := dummyPtr의 next로 이동합니다.
- 그 외의 경우 (중복 구간 시작): prev := head, head := head의 next로 설정한 뒤, head가 null이 아니면서 head의 값이 prev의 값과 같은 동안 계속 앞으로 이동하여 중복 구간 전체를 건너뜁니다.
- 반복이 종료되면 더미 노드의 next, 즉 새로 구성된 리스트의 헤드를 반환합니다.
이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 노드를 생성하지 않고 기존 노드를 재배열하므로 공간 복잡도는 O(1)입니다.
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(-1);
ListNode* prev = NULL;
ListNode* dummyPtr = dummy;
ListNode* nextNode;
while(head){
if(!head->next || head->val != head->next->val){
dummyPtr->next = head;
ListNode* temp = head->next;
head->next = NULL;
head = temp;
dummyPtr = dummyPtr->next;
} else {
prev = head;
head = head->next;
while(head && head->val == prev->val){
prev = head;
head = head->next;
}
}
}
return dummy->next;
}
};
main(){
Solution ob;
vector<int> v = {1,1,1,2,2,3,5,6,6,7,8};
ListNode *head = make_list(v);
print_list(ob.deleteDuplicates(head));
}입력
[1,1,1,2,2,3,5,6,6,7,8]
출력
[3, 5, 7, 8]