Remove Duplicates from Sorted List

Условие

Дан отсортированный по возрастанию односвязный список. Необходимо удалить все дубликаты, чтобы каждый элемент встречался только один раз. Нужно вернуть связанный список с уникальными элементами в том же порядке.

Примеры

Input: head = [1, 1, 2]

Output: [1, 2]

Input: head = [1, 1, 2, 3, 3]

Output: [1, 2, 3]

Решение

// Определение структуры узла связанного списка
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 */
fun deleteDuplicates(head: ListNode?): ListNode? {
    var current = head
    // Проходим по всему списку, пока не достигнем конца
    while (current != null && current.next != null) {
        // Если текущий элемент совпадает со следующим, пропускаем дубликат
        if (current.`val` == current.next?.`val`) {
            current.next = current.next?.next // Убираем дубликат, перескакивая через него
        } else {
            current = current.next // Иначе продолжаем движение по списку
        }
    }
    return head // Возвращаем модифицированный список
}

Временная сложность

O(n), где n — количество узлов в списке. Мы проходим по каждому узлу один раз.

Пространственная сложность

O(1), так как используется константное количество дополнительной памяти.