Удаление узла в одиночном списке ссылок

Question

Как удалить узел в отдельном списке ссылок только с одним указателем, указывающим на удаляемый узел?

[Начало и конец указатели не известны, имеющаяся информация является указателем на узел, который должен быть удален]

Answer 1

Вы можете удалить узел без получения предыдущего узла, имея его имитировать следующий узел и удалить, что один вместо этого:

void delete(Node *n) { 
    if (!is_sentinel(n->next)) { 
    n->content = n->next->content; 
    Node *next = n->next; 
    n->next = n->next->next; 
    free(next); 
    } else { 
    n->content = NULL; 
    free(n->next); 
    n->next = NULL; 
    } 
} 

Как вы можете видеть, вам нужно будет иметь дело специально для последнего элемента. Я использую специальный узел в качестве сторожевого узла для отметки окончания, который имеет content и next be NULL.

UPDATE: линии Node *next = n->next; n->next = n->next->next в основном перемешивает содержимое узла и освобождает узел: Изображение, которое вы получаете ссылку на узел B должен быть удален в:

A   /To be deleted 
    next ---> B 
       next ---> C 
          next ---> *sentinel* 

Первый шаг n->content = n->next->content: скопировать содержимое следующего узла к узлу, чтобы быть "удален":

A   /To be deleted 
    next ---> C 
       next ---> C 
          next ---> *sentinel* 

Затем измените next точки:

A   /To be deleted 
    next ---> C  /---------------- 
       next ---| C   | 
          next ---> *sentinel* 

Реально свободный следующий элемент, попадая в конечном случае:

A   /To be deleted 
    next ---> C 
       next ---> *sentinel* 

Answer 2

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

Answer 3

Невозможно.

Есть хаки, имитирующие удаление.

Но ни один из них фактически не удалит узел, на который указывает указатель.

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

Вы можете найти обсуждение на SO here.