Единый связанный список - Удалить из середины

Question

Я пытаюсь выяснить алгоритм удаления из середины связанного списка ..

Моя идея состоит в том, чтобы просмотреть список, найти узел непосредственно перед тем узлом, который я хочу удалить, вызвать егоNprev и установите Nprev в Nnext, где Nnext - после узла, чтобы удалить Ndelete.

Итак Nprev -> Ndelte -> Nnext.

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

Я делал это с ошибками сегмента, потому что я назначаю указатели вне диапазона, который я предполагаю.Это очень грязный алгоритм, который у меня есть, со многими операторами if else.

Есть ли более простой способ сделать это?

В основном мне нужно пройти по списку, применить функцию ккаждый узел для проверки, если это правда или ложь.Если false, я удаляю узел.Удаление первого и последнего не так сложно, но среднее затруднило меня.

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

Я использовал это: http://www.cs.bu.edu/teaching/c/linked-list/delete/

, но алгоритм перед шагом 4 удаляет только первый узел в моем списке и не делаетделай большеКак я могу изменить это?

Они также приводят рекурсивный пример, но я этого не понимаю и пугаюсь.

Answer 1

Вот пример того, что я использую для поиска и удаления по индексу:

С учетом этой структуры : (Может также быть адаптировано к другим структурам со ссылками на себя)

struct node
{
    S s;
    int num;
    char string[10];
    struct node *ptr;
};
typedef struct node NODE;

Используйте это , чтобы удалить элемент из середины списка (по индексу)

int remove_by_index(NODE **head, int n) /// tested, works 
{
    int i = 0;
    int retval = -1;
    NODE * current = *head;
    NODE * temp_node = NULL;

    if (n == 0) {
        return pop(head);
    }

    for (int i = 0; i < n-1; i++) {
        if (current->ptr == NULL) {
            return -1;
        }
        current = current->ptr;
    }

    temp_node = current->ptr;
    retval = temp_node->num;
    current->ptr = temp_node->ptr;
    free(temp_node);

    return retval;

}

Answer 2

Сначала вам нужно найти средний узел.Хорошо, возьмите 3 указателя: быстрый, медленный, prev с быстрым движением с удвоенной скоростью замедления и сохранением адреса узла, предшествующего медленному.то есть *slow=&head,*fast=&head,prev=Null пересекает список и когда fast=NULL slow будет указывать на средний узел, если число элементов нечетное, а prev будет хранить адрес узла, предшествующего среднему узлутак просто prev->next=slow->next.