gul_tech (gul_tech) wrote,
gul_tech
gul_tech

Category:

Программирование

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

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 - начало нового списка.

Tags: задачка
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments