Помогите разобраться как работает структура
решал простые задачки на LeetCode ну и наткнулся на следующую задачку где фигурирует вот такая вот структура.
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
Из условий я понял что эта задачка создает грубо говоря список. И мне необходимо объединить 2 таких списка. Я пытался обращаться через оператор [] что бы получить значение из списка, но не получилось. Помоги те понять как работает эта структура. Хочу понять как с ней взаимодействовать
Ответы (1 шт):
Итак, по пунктам:
1. Чтобы объединить два связных списка, нужно дойти до последнего элемента 1-го списка и в его поле next записать адрес 2-го списка. Пример реализации:
void union_list(ListNode* L1, ListNode* L2) {
ListNode* ptr = L1;
while (ptr->next != nullptr)ptr = ptr->next;
ptr->next = L2;
}
Естественно у вас не получилось обратиться к элементу структуры через []. Точно также вы не сможете сложить две структуры или умножить одну на другую. Чтобы эти операции были возможны, вам надо самостоятельно определить их поведение через перегрузку операторов.
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
int operator[](unsigned index)
{
ListNode* ptr = this;
for (int i = 0; i < index; ++i)ptr = ptr->next;
return ptr->val;
}
};
Теперь при обращении через [i] будет возвращаться i-й элемент в структуре, если считать за нулевой тот нод, к которому применена операция. Но следует учитывать, что такая операция имеет асимптотику O(i), где i - индекс элемента.
3. Взаимодействие со структурой:
Пусть у нас есть структура ListNode a.
обращение к первому элементу структуры - a.val`;
ко второму - a.next->val;
к третьему - a.next->next->val;
и тд.
добавить элемент в a - x.next = new ListNode; где x - последний нод объекта а
вставить элемент y после нода x -
y.next = x.next;
x.next = &y;