II2022/08/04に公開LeetCodetechhttps://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/昇順にソートされた数値のリストが渡され、リストの中で数値が重複している部分を除外してリストを返す、という問題。ソートされているので、必然的に重複部分は連続している。基本的な考えとしてはノードを走査するカーソルを最初から最後まで一つずつ進め、重複があるか(今の値と次の値が同一であるか)をしらべていく現在のカーソル位置以前で、重複がない最後のノードを記憶しておく(便宜上Prevノードと呼ぶ)重複を見つけたら、重複が終わるまでカーソルを進め、重複が終わったところでPrevノードと次のノードとを接続するという形になる。例をもとにかんたんに図示する。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になるため、走査を終了する。最後はダミーノードの次のノードを返せば終了。Proよくある質問LinksX(Twitter)GitHubメディアキットLegal利用規約プライバシーポリシ。