04. Remove Duplicates from Sorted List II

読了目安約2分

Linked List / LeetCode 82 (Medium) — 重複した値のノードをすべて取り除き、一度だけ現れた値を残す。

この章の目次

問題

LeetCode 82. Remove Duplicates from Sorted List II（Medium / カテゴリ: Linked List）

値が昇順に並んだ連結リストの先頭 head が与えられます。 2 回以上現れた値のノードをすべて取り除き、一度だけ現れた値のノードを残したリストを返してください。 83 と違い、重複した値は 1 個も残しません。

考え方

ヒント 1

先頭ノード自体が削除されることがあります。先頭の前にダミーノードを 1 つ置くと、先頭の削除もそれ以外と同じ処理で書けます。

ヒント 2

「残ると確定した最後のノード prev」と「調べているノード」の 2 つを持ちます。次のノードが同じ値なら、その値のノードを最後まで読み飛ばし、prev.next を飛ばした先へつなぎます。

Swift 実装のポイント

番兵は、場合分けをなくすために置くダミーノードです。dummy.next = head から始め、答えは dummy.next で返します。
重複はノードの同一性ではなく値の一致なので、== で比べます。
prev を進めてよいのは、注目ノードが「重複なし」と確定したときだけです。

模範解答

Swift
class Solution {
    func deleteDuplicates(_ head: ListNode?) -> ListNode? {
        let dummy = ListNode(0)
        dummy.next = head
        var prev = dummy
        var node = head
        while let n = node {
            if let next = n.next, next.val == n.val {
                var cur: ListNode? = n
                while let c = cur, c.val == n.val {
                    cur = c.next
                }
                prev.next = cur
                node = cur
            } else {
                prev = n
                node = n.next
            }
        }
        return dummy.next
    }
}

計算量: O(n) 時間、O(1) 追加メモリ。