82.remove-dpulicates-from-sorted-list-ii.md

82. Remove Duplicates from Sorted List II

We can use a sentinel node to handle the edge case where the first node is a duplicate. We can use three pointers to keep track of the previous, current, and next nodes. We can loop until the current node is distinct from the next node. Then we can update the previous node to point to the next node.

s -> 1 -> 1 -> 1
p    c    n
p         c    n

s -> 1 -> 1 -> 2
p    c    n
p         c    n
p.next = n

fun deleteDuplicates(head: ListNode?): ListNode? {
    val sentinel = ListNode(-1000)
    sentinel.next = head

    // The node before the start of duplicate
    var previous: ListNode? = sentinel
    var current: ListNode? = head
    var next: ListNode? = head?.next
    while (next != null) {
        if (current?.`val` == next?.`val`) {
            // loop until item becomes distinct
            while (current?.`val` == next?.`val`) {
                current = next
                next = next?.next
            }

            // pointer to the distinct item
            previous?.next = next
        } else {
            previous = current
        }
        current = next
        next = next?.next
    }
    return sentinel.next
}

Test Cases

1 -> 1
1 -> 1 -> 2 -> 2
1 -> 2 -> 2 -> 2 -> 3 -> 3