Как удалить промежуточный узел из связанного списка

Question

У меня есть отдельный список. Если я хочу удалить известный элемент из этого связанного списка, что я могу сделать?

Например: Узел * head; (44) Узел * хвост; (39)

Связанный список: 44 27 59 13 45 39 Мы хотим удалить 45 из него. и получите: 44 27 59 13 39

Я только выяснил, что удалить первый элемент из списка (если элемент (нужно удалить) - это первый элемент списка). Я получил: head = head-> next;

Как удалить промежуточный узел из списка?

Answer 1

13 будет указывать 45 в качестве следующего элемента, просто измените его следующий элемент на 39. И освободите 45 из памяти, чтобы сохранить память чистой от мусора.

Answer 2

Посмотрите на значение в следующем узле, если есть значение. Если это значение, которое вы ищете, то следующий узел - тот, который нужно удалить, поэтому вы добавляете следующий элемент следующего узла к следующему элементу следующего узла после сохранения указателя на следующий узел, чтобы вы могли удалить Это.

// Assuming head is a non-const reference variable (or a global variable) 
if (head == NULL) 
    return; 
if (head->value == wanted) 
{ 
    head = head->next; 
    return; 
} 
for (Node *curr = head; curr->next != NULL; curr = curr->next) 
{ 
    if (curr->next->value == wanted) 
    { 
     Node *old = curr->next; 
     curr->next = curr->next->next; 
     delete old; 
     return; 
    } 
} 
return; // Possibly after reporting that the value wanted was not found 

Answer 3

Сначала найдите элемент, который хотите удалить. Не забудьте обработать, когда элемент не существует:

Node* find(Node* head, int value) { 
    do { 
     if (head->value == value) return head; 
     head = head->next; 
    } while (head); 
    return nullptr; 
} 

Затем вы хотите подключить next PTR в предыдущего узла к следующим узлу. В односвязном списке вы можете отслеживать предыдущий узел с использованием локальной переменной. Не забудьте обработать, если узел вы хотите удалить это голова (т.е. нет предыдущего узла), или, если узел является хвост (т.е. нет следующего узла):

Node *previous = nullptr; 
do { 
    if (head->value == value) { 
     if (previous != nullptr) { 
      previous->next = head->next; 
     } 
     if (head == tail) { 
      tail = previous; 
     } 
     return; 
    } 
    previous = head; 
    head = head->next; 
} while (head); 

Answer 4

Продумайте проблемы.

Вам нужна петля, чтобы пересечь все узлы, пока не найдете тот, который вы ищете. Скажем, у вас есть Node * curr, как показано на главу.

while(curr != null) 

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

if (curr->value == node_you_are_looking_for->value) 

Если это соответствующий узел, удалите этот узел. У вас есть два указателя для обновления ссылок.

prev->next = curr->next; 
prev = curr; 
curr = curr->next; 
prev->next = null; 
delete(prev); 

Else продолжать перемещаться по списку.

prev = curr; 
curr= curr->next; 

Затем вы можете собрать все эти шаги и написать рабочую программу.

Answer 5

Этот псевдо-код может помочь вам: -

void remove(int key) { 
    Node* p = head->next; 
    Node*prev = head; 
    while(p!=NULL) { 

    if(p->data==key) { 
     prev->next = p->next; 
     free(p); 
     break;   
    } 
    prev = p; 
    p = p->next; 
    } 
}