💬

LeetCode 82. Remove Duplicates from Sorted List II

2022/08/04に公開約2,400字

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

昇順にソートされた数値のリストが渡され、リストの中で数値が重複している部分を除外してリストを返す、という問題。
ソートされているので、必然的に重複部分は連続している。

基本的な考えとしては

  • ノードを走査するカーソルを最初から最後まで一つずつ進め、重複があるか(今の値と次の値が同一であるか)をしらべていく
  • 現在のカーソル位置以前で、重複がない最後のノードを記憶しておく(便宜上Prevノードと呼ぶ)
  • 重複を見つけたら、重複が終わるまでカーソルを進め、重複が終わったところでPrevノードと次のノードとを接続する

という形になる。

例をもとにかんたんに図示する。
リスト:1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> 6

処理の簡略化のため、最初にダミーとなるノードを接続しておく。
Prevノードはダミーノード、カーソルは1の位置にある。

カーソルの値1と次の値2を比較する。
値が異なり重複していないので、Prevノードとカーソルを一つ進める。

カーソルの値2と次の値3を比較する。
重複ではないため、同様にPrevノードとカーソルを一つ進める。

カーソルの値3と次の値3が同一のため、重複を検出した。
Prevノードはそのままで、重複が終わるまでカーソルを進める。

カーソルの値3と次の値4が異なるため、重複が終わったと判断。
Prevノードを次のノードに接続する。Prevノードの位置はそのまま。

カーソルを次に移動する。

カーソルの値4と次の値4が同一のため、また重複を検出した。
Prevノードはそのままで、重複が終わるまでカーソルを進める。

カーソルの値4と次の値5が異なるため、重複が終わったと判断。
Prevノードを次のノードに接続しなおす。Prevノードの位置はそのまま。

カーソルを次に進める。
カーソルの値5と次の値6とが異なるため、重複ではない。

PrevノードをPrevの接続先のノードに移動する。
カーソルの次の値はNULLになるため、走査を終了する。

最後はダミーノードの次のノードを返せば終了。

class Solution {
    function deleteDuplicates($head) {
        $result = new stdClass();
        $result->next = $head;
        $result->value = null;

        $prev = $result;
        while ($head) {
            if ($head->next !== null && $head->val === $head->next->val) {
                while ($head->next !== null && $head->val === $head->next->val) {
                    $head = $head->next;
                }
                $prev->next = $head->next;
            } else {
                $prev = $prev->next;
            }
            $head = $head->next;
        }
        return $result->next;
    }
}

Discussion

ログインするとコメントできます