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