Как удалить элемент из списка?, программирование Опции Рейтинг

[ierton]

Весь форум не читал, прошу прощения если задача с бородой. Говорят, что спрашивали на собеседовании в гугле.

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

Короче говоря:

struct Item { void* data; struct Item * next; } ;

void delete_item(struct Item * item)
{
???
}

Список конечный, признак последнего элемента - p.next == 0. Язык - С.

[De_Bill]

Ну там какой-то странный вариант дфса конечно получается ну да ладно. хотя да, это вообще будет не дфс

идем по некстам до конца первого списка, создаем элементы второго, пока что только с полями некст
дальше берем i-тый элемент первого списка(Аi), и соответствующий ему эл-т второго списка (Bi)
пишем
Item1=A1
Item2=A2
while (Item1!=Ai.random){
Item1=Item1.next
Item2=Item2.next
}
Bi.random=Item2;

Ну и прокручиваем это для каждого i

Конечно тут две лишних переменных, но, думаю, это ничего

[Powered by Java]

Ну там какой-то странный вариант дфса конечно получается ну да ладно. хотя да, это вообще будет не дфс

идем по некстам до конца первого списка, создаем элементы второго, пока что только с полями некст
дальше берем i-тый элемент первого списка(Аi), и соответствующий ему эл-т второго списка (Bi)
пишем
Item1=A1
Item2=A2
while (Item1!=Ai.random){
Item1=Item1.next
Item2=Item2.next
}
Bi.random=Item2;

Ну и прокручиваем это для каждого i

Конечно тут две лишних переменных, но, думаю, это ничего

т.е. рандом элементы искать для каждого элемента нового списка? Слишком уж долго... О(n^2)...