Программирование
Не очень сложная, но интересная задачка.
Есть односвязный список. В каждом элементе есть некое значение, ссылка на следующий элемент списка и ссылка на какой-то произвольный элемент этого списка.
Нужно сделать независимую копию этого списка.
Ограничения: время выполнения должно быть линейно от длины списка, количество дополнительной памяти (помимо старого и нового списка) константно, т.е. не должно зависеть от длины списка.
Никакими блокировками и параллельным доступом можно не заморачиваться (типа один поток).
UPD: Ни одного решения не дождался.
Эх... :(
[Решение]
На первом проходе из списка A->B->C->D делаем копию каждого элемента, и указатели next ставим таким образом, чтобы получился список A->A'->B->B'->C->C'->D->D', т.е. нечто вроде
(memdup() - это malloc() и memcpy(), по аналогии с strdup()).
Вторым проходом подправляем rnd-указатели (на произвольный элемент списка) для новых элементов - тот, что указывал на X, теперь будет указывать на X->next, который X':
Третьим проходом делаем из одного длинного списка A->A'->B->B'->... два отдельных, оригинальный A->B->C->D и новый A'->B'->C'->D':
Всё.
Три прохода, две дополнительные переменные - p, p1.
newhead - начало нового списка.
Есть односвязный список. В каждом элементе есть некое значение, ссылка на следующий элемент списка и ссылка на какой-то произвольный элемент этого списка.
Нужно сделать независимую копию этого списка.
Ограничения: время выполнения должно быть линейно от длины списка, количество дополнительной памяти (помимо старого и нового списка) константно, т.е. не должно зависеть от длины списка.
Никакими блокировками и параллельным доступом можно не заморачиваться (типа один поток).
UPD: Ни одного решения не дождался.
Эх... :(
[Решение]
На первом проходе из списка A->B->C->D делаем копию каждого элемента, и указатели next ставим таким образом, чтобы получился список A->A'->B->B'->C->C'->D->D', т.е. нечто вроде
for (p=head; p; p=p->next) { p1=memdup(p); p->next = p1; p=p1; }
(memdup() - это malloc() и memcpy(), по аналогии с strdup()).
Вторым проходом подправляем rnd-указатели (на произвольный элемент списка) для новых элементов - тот, что указывал на X, теперь будет указывать на X->next, который X':
for (p=head->next; p; p=p->next->next) { p->rnd = p->rnd->next; }
Третьим проходом делаем из одного длинного списка A->A'->B->B'->... два отдельных, оригинальный A->B->C->D и новый A'->B'->C'->D':
newhead = head->next; for (p=head, p1=newhead; p; p=p->next, p1=p1->next) { p->next = p->next->next; p1->next = p1->next->next; }
Всё.
Три прохода, две дополнительные переменные - p, p1.
newhead - начало нового списка.