💬
LeetCode 82. 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