203. Remove Linked List Elements

Задача

Даны голова списка и значение val. Удалите все узлы со значением val и верните новую голову.

Примеры

Пример 1

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

Пример 2

Input: head = [], val = 1
Output: []

Пример 3

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

Решение

Решение

/**
 * Time Complexity: O(n) - проходим по списку один раз
 * Space Complexity: O(1) - используем только константное количество дополнительной памяти (dummy, prev, current)
 */
var removeElements = function(head, val) {
    const dummy = new ListNode(null, head);
 
    let prev = dummy;
    let current = prev.next;
 
    while (current) {
        if (current.val === val) {
            prev.next = current.next;
            current = prev.next
        } else {
            prev = current;
            current = current.next;
        }
    }
 
    return dummy.next;
};

Решение 2

/**
 * Идея: обрабатываем список с конца к началу через рекурсию. Сначала рекурсивно очищаем хвост, затем решаем для текущего узла.
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(n) - из-за стека вызовов рекурсии
 */
var removeElements = function(head, val) {
    if (!head) return null;
 
    head.next = removeElements(head.next, val);
 
    return head.val === val ? head.next : head;
};