備忘録 LeetCode-83. Remove Duplicates from Sorted List

はじめに

この記事はアルゴリズム振り返り用メモ.
言語化練習用に作成した記事です.

URL

Remove Duplicates from Sorted List

対象者

特になし

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        //アドレスをコピーする
        ListNode* copy = head;
        
        //現在の位置 && 次の位置が nullになるまで続ける
        while(copy != nullptr && copy->next != nullptr){
            //現在の位置　と　次の位置が一致している場合　
            //次の位置　を　次の次のnodeで上書きする
            if(copy->val == copy->next->val)copy->next = copy->next->next;
            //一致していない場合 次のnodeに更新する
            else copy = copy->next;
        }

        //アドレスを変更していたのでheadを返す
        return head;
    }
};

結果

Runtime: 17 ms, faster than 50.06% of C++ online submissions for Remove Duplicates from Sorted List.
Memory Usage: 11.5 MB, less than 97.36% of C++ online submissions for Remove Duplicates from Sorted Lis

詳細

headのアドレスをコピーする

現在の位置と次の位置のvalが一致している場合は
次のnodeを次の次のnodeに上書きする
というのを繰り返して連続した重複値を消去している。

headのアドレスをコピーして編集していたため
headが間接的に更新されるので
headを返す.

参照

動画

おわりに

今回の問題は前回のLeetCode-142. Linked List Cycle IIに比べて簡単に感じた