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

  • Рейтинг провайдеров

    Изменение позиций в топе как России, так и Украины. ReTN и ITSystems уступили лидерство. Сейчас среди российских провайдеров по размеру клиентского…

  • Рейтинг провайдеров

    Давно не писал про рейтинг. Поступил с ним по-сисадмински: дал инструменты для самостоятельного его просмотра, включая графики, и на постинги забил.…

  • Рейтинг провайдеров - графики

    Сделал рисовалку графиков на основе рейтинга провайдеров. Вот пример её работы: Видны отдельные пики - это из-за крупных роутликов какой-то…

  • 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