JuniorКодОчень частоЕщё не отвечали
Для структуры типа односвязный список напишите функцию вставки элемента
Дан односвязный список из Node. Реализуйте вставку в начало, в конец и на произвольную позицию (0-индексированную). Каждая функция возвращает (возможно, новый) указатель на голову.
Требования:
- Вставка в начало — O(1).
- Вставка на позицию k проходит только до предшественника (O(k)).
- Обработайте вставку на позицию 0 (она меняет голову) и позицию вне диапазона.
struct Node {
int val;
Node* next;
explicit Node(int v, Node* n = nullptr) : val(v), next(n) {}
};
Node* insertFront(Node* head, int val);
Node* insertBack(Node* head, int val);
Node* insertAt(Node* head, int val, int pos); // ваш код здесьДопишите реализацию.
Вставка в голову — O(1): новый узел, его next → старая голова, обновить голову. На позицию k — O(k): дойти до предшественника. В хвост без tail-указателя — O(n).
- ✗Забывать отдельно обрабатывать вставку на позицию 0 (голова)
- ✗Пройти на один узел дальше — нужен узел перед точкой вставки, а не на ней
- ✗Не обновлять указатель на голову при вставке на позицию 0
- →Как вставить элемент в уже отсортированный список с сохранением порядка?
- →Какова сложность построения отсортированного списка последовательными вставками в порядке?
Оглавление
Задача
Реализуйте функции для вставки элемента в начало, конец и заданную позицию односвязного списка.
Решение
#include <cassert>
#include <stdexcept>
struct Node {
int val;
Node* next;
explicit Node(int v, Node* n = nullptr) : val(v), next(n) {}
};
// Вставка в начало — O(1)
Node* insertFront(Node* head, int val) {
return new Node(val, head);
}
// Вставка в конец — O(n)
Node* insertBack(Node* head, int val) {
Node* newNode = new Node(val);
if (!head) return newNode;
Node* cur = head;
while (cur->next) cur = cur->next;
cur->next = newNode;
return head;
}
// Вставка на позицию pos (0-indexed) — O(pos)
Node* insertAt(Node* head, int val, int pos) {
if (pos == 0) return insertFront(head, val);
Node* cur = head;
for (int i = 0; i < pos - 1; ++i) {
if (!cur) throw std::out_of_range("position out of range");
cur = cur->next;
}
cur->next = new Node(val, cur->next);
return head;
}
int length(Node* head) {
int n = 0; while (head) { ++n; head = head->next; } return n;
}
int nthVal(Node* head, int n) {
while (n--) head = head->next; return head->val;
}
int main() {
Node* list = nullptr;
list = insertBack(list, 1);
list = insertBack(list, 3);
list = insertFront(list, 0);
list = insertAt(list, 2, 2); // 0 -> 1 -> 2 -> 3
assert(length(list) == 4);
assert(nthVal(list, 0) == 0);
assert(nthVal(list, 1) == 1);
assert(nthVal(list, 2) == 2);
assert(nthVal(list, 3) == 3);
}Ключевые моменты
- Вставка в голову: O(1) — самая дешёвая операция.
- Вставка в хвост: O(n) без указателя на хвост.
- Вставка на позицию k: необходим узел на позиции k-1 (предшественник).
- Не забывайте обновлять
head, если он меняется (позиция 0).
Оглавление
