?

Log in

No account? Create an account
 
 
05 October 2013 @ 03:47 pm
Программирование  
Не очень сложная, но интересная задачка.
Есть односвязный список. В каждом элементе есть некое значение, ссылка на следующий элемент списка и ссылка на какой-то произвольный элемент этого списка.
Нужно сделать независимую копию этого списка.
Ограничения: время выполнения должно быть линейно от длины списка, количество дополнительной памяти (помимо старого и нового списка) константно, т.е. не должно зависеть от длины списка.
Никакими блокировками и параллельным доступом можно не заморачиваться (типа один поток).

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

 
 
 
Сергій Колісникskolk on October 7th, 2013 11:16 am (UTC)
В копии списка на всех проходах кроме последнего, поле ссылки на следующий можно использовать по своему усмотрению?
gul_tech: gulgul_tech on October 7th, 2013 09:32 pm (UTC)
Да.
Всё копирование списка - одна транзакция. Промежуточные состояния неважны. Главное, чтобы в конце получился нужный результат.
Сергій Колісникskolk on November 18th, 2013 12:45 pm (UTC)
Надо было ставить задачу как декларацию вызова. Была бы подсказка :) А так список-оригинал воспринимается как const :( (возможно, расположенный в недоступной на запись памяти).
bormal: pic#110275107bormal on October 22nd, 2013 04:13 am (UTC)
Красивое решение.
А я так ничего и не придумал : (