Опыт - это то, что мы получаем вместо того, что хотели

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

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