정렬된 연결 목록이 있다고 가정합니다. 각 요소가 한 번만 표시되도록 모든 중복 항목을 삭제해야 합니다.
따라서 입력이 [1,1,2,3,3,3,4,5,5]와 같으면 출력은 [1,2,3,4,5]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
더미 :=값 -inf
로 새 노드를 만듭니다. -
더미의 다음 :=머리
-
curr =더미
-
curr이 0이 아닌 동안 수행 -
-
다음 =현재의 다음
-
동안(next는 null이 아니며 next의 val은 curr의 val과 동일) 다음을 수행합니다. -
-
다음 :=다음의 다음
-
-
curr의 다음 :=다음
-
curr :=다음
-
-
더미 다음으로 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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, ]