Problem
Key Idea
์ด์ ๋ ธ๋์ ๊ฐ๊ณผ ์ถํํ์๋ฅผ cachingํ๋ฉฐ List๋ฅผ ์ํํ๋ค.
- \(curVal\): ์ด์ ๋ ธ๋์ ๊ฐ
- \(cnt\): ๊ทธ ๊ฐ์ ์ถํ ํ์
List์ ๋์ด๋ ๋ค๋ฅธ \(val\)์ ๊ฐ์ง ๋ ธ๋๋ฅผ ๋ง๋ฌ์ ๋, \(count = 1\)์ธ ๊ฒฝ์ฐ์๋ง ์ ๋ต List์ ๋ ธ๋ ์ถ๊ฐ.
๊ตฌํํ ๋๋ ๊ฐ์์ ์ฒซ ๋ ธ๋๋ฅผ ๋จผ์ ๋ง๋ค์ด๋๊ณ , ์ ๋ต ๋ฐํ์์ ๊ทธ ๊ฐ์ ๋ ธ๋์ next๋ฅผ ๋ฐํํ๋ฉด ํธํ๋ค.
Implementation
/**
* written: 2021. 12. 31. Fri. 16:49:01 [UTC+9]
* jooncco์ mac์์.
**/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// ์ ๋ต List
ListNode *ansHead= new ListNode();
ListNode *ansCur= ansHead;
int curVal= -101, cnt= 0;
ListNode *cur= head;
while (cur != NULL) {
if (cur->val == curVal) ++cnt;
else {
if (cnt == 1) {
// ์ค๋ณต๋์ง ์์ ๋
ธ๋๋ฅผ ์ ๋ต List์ ์ถ๊ฐ
ansCur->next= new ListNode(curVal);
ansCur= ansCur->next;
}
// ์๋ก์ด ๊ฐ counting ์์
curVal= cur->val;
cnt= 1;
}
cur= cur->next;
}
// ๋ฆฌ์คํธ์ ๋
if (cnt == 1) ansCur->next= new ListNode(curVal);
return ansHead->next;
}
};
- Time: \(O(n)\)
Leave a comment