Remove Linked List Elements

Условие

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

Примеры

Input: head = [1, 2, 6, 3, 4, 5, 6], val = 6

Output: [1, 2, 3, 4, 5]

Input: head = [], val = 1

Output: []

Input: head = [7, 7, 7, 7], val = 7

Output: []

Решение

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
fun removeElements(head: ListNode?, `val`: Int): ListNode? {
    // Создаем фиктивный узел для упрощения работы с началом списка
    val dummy = ListNode(0)
    dummy.next = head
    
    // Указатель на текущий узел
    var current: ListNode? = dummy
    
    // Проходим по списку
    while (current?.next != null) {
        if (current.next?.`val` == `val`) {
            // Пропускаем узел, если его значение равно искомому
            current.next = current.next?.next
        } else {
            // Переходим к следующему узлу
            current = current.next
        }
    }
    
    // Возвращаем измененный список, начиная с первого узла после фиктивного
    return dummy.next
}

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

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

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

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