Удаление узла

легко

# решено

Дан указатель на голову односвязного списка head и целое число x. Нужно вернуть список, в котором удалены все узлы со значением, равным x. Если после удаления список стал пустым, нужно вернуть нулевой указатель.

Пример 1:

Ввод: head = [6,7,1,5,9], node = 5
Вывод: [6,7,1,9]
Объяснение: Вам задан четвёртый узел со значением 5, связанный список должен стать 6 -> 7 -> 1 -> 9 после вызова вашей функции.

Пример 2:

Ввод: head = [11,2,6,3], node = 11
Вывод: [2,6,3]
Объяснение:  Вам задан первый узел со значением 11, связанный список должен стать 2 -> 6 -> 3 после вызова вашей функции.

Ограничения:

len(head) ≥ 1
Узел node всегда существует в списке и не является последним элементом

/**
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public static ListNode RemoveElements(ListNode head, int val) {
        // создаём фиктивный узел перед головой списка
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // итерируемся начиная с фиктивного узла
        ListNode node = dummy;
        while (node.next != null) {
            // если значение совпадает, пропускаем следующий узел
            if (node.next.val == val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return dummy.next;
    }
}

#include <vector>

using namespace std;

/**
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

ListNode* removeElements(ListNode* head, int val) {
    // создаём фиктивный узел перед головой списка
    ListNode dummy(0);
    dummy.next = head;

    // итерируемся начиная с фиктивного узла
    ListNode* node = &dummy;
    while (node->next != nullptr) {
        // если значение совпадает, пропускаем следующий узел
        if (node->next->val == val) {
            node->next = node->next->next;
        } else {
            node = node->next;
        }
    }
    return dummy.next;
}

package main

/**
 * type ListNode struct {
 *     Val  int
 *     Next *ListNode
 * }
 */

func removeElements(head *ListNode, val int) *ListNode {
    // создаём фиктивный узел перед головой списка
    dummy := &ListNode{Val: 0, Next: head}

    // итерируемся начиная с фиктивного узла
    node := dummy
    for node.Next != nil {
        // если значение совпадает, пропускаем следующий узел
        if node.Next.Val == val {
            node.Next = node.Next.Next
        } else {
            node = node.Next
        }
    }
    return dummy.Next
}

import java.util.*;

/**
 * class ListNode {
 *     Integer val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(Integer val) { this.val = val; }
 *     ListNode(Integer val, ListNode next) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public static ListNode removeElements(ListNode head, int val) {
        // создаём фиктивный узел перед головой списка
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // итерируемся начиная с фиктивного узла
        ListNode node = dummy;
        while (node.next != null) {
            // если значение совпадает, пропускаем следующий узел
            if (node.next.val == val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return dummy.next;
    }
}

from list_node import ListNode

# class ListNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next

def remove_elements(head: Optional[ListNode], val: int) -> Optional[ListNode]:
    # создаём фиктивный узел перед головой списка
    dummy = ListNode(0)
    dummy.next = head

    # итерируемся начиная с фиктивного узла
    node = dummy
    while node.next != None:
        # если значение совпадает, пропускаем следующий узел
        if node.next.val == val:
            node.next = node.next.next
        else:
            node = node.next
    return dummy.next

import { ListNode } from './listNode.js';

/**
 * class ListNode {
 *     constructor(val, next) {
 *         this.val = val;
 *         this.next = (next === undefined ? null : next);
 *     }
 * }
 */

/**
 * @param {ListNode} head
 * @param {number} val
 * @returns {ListNode}
 */
export function removeElements(head /*: ListNode | null */, val /*: number */) {
    // создаём фиктивный узел перед головой списка
    let dummy = new ListNode(0);
    dummy.next = head;

    // итерируемся начиная с фиктивного узла
    let node = dummy;
    while (node.next !== null) {
        // если значение совпадает, пропускаем следующий узел
        if (node.next.val === val) {
            node.next = node.next.next;
        } else {
            node = node.next;
        }
    }
    return dummy.next;
}

Оценка сложности

Время: O(n), где n - количество узлов в списке head
Память: O(1)