Задача
Є однозв’язний список кожен елемент якого крім даних та вказівника на наступний елемент також містить вказівник на будь-який елемент з цього ж списку. Треба написати функцію “глибокого” копіювання такого списку – так щоб у копії випадкові вказівники вказували на ті ж елементи що і в оригіналі.
Копіювання повинно виконуватися за лінійний час без виділення додаткової пам’яті.
Рішення 1
Спочатку створюємо копію кожного елемента і робимо наступні зміни:
- вказівники на наступний і випадковий елемент у копії встановлюємо у значення випадкового вказвника оригінала
- вказівник на випадковий елемент в оригіналі встановлюємо в адресу копії
На наступному проході (йдемо по оригінальному списку) встановлюємо “випадкові” вказівники в копіях.
На третьому проході відновлюємо “випадкові” вказівнику оригіналу з вказівників на наступний елемент копії, і одночасно встановлюємо вказівник на наступний елемнт в копіях.
list_item* copy_list(list_item *src) { list_item *prevDst = NULL, *headDst = NULL; for (list_item *curSrc = src, *nextSrc = NULL; curSrc; curSrc = curSrc->next) { list_item *newDst = new list_item; if (!headDst) headDst = newDst; newDst->value = toupper(curSrc->value); newDst->rnd = curSrc->rnd; newDst->next = curSrc->rnd; curSrc->rnd = newDst; } // build rnd pointers for copy for (list_item *curSrc = src; curSrc; curSrc = curSrc->next) { list_item *curDst = curSrc->rnd; if (curDst->rnd) curDst->rnd = curDst->rnd->rnd; } // restore source rnd pointer and copy next pointer for (list_item *curSrc = src, *prevDst = NULL; curSrc; curSrc = curSrc->next) { list_item *curDst = curSrc->rnd; list_item *prevSrc = curDst->next; curSrc->rnd = prevSrc; if (prevDst) prevDst->next = curDst; if (!curSrc->next) curDst->next = NULL; prevDst = curDst; } return headDst; }
Рішення 2
Насправді нам не обов’язково двічі копіювати вказвники. Натомість кожен новий елемент-копію ми можемо додати у оригінальний список одразу за зкопійованим елементом.
Оригінал:
Додаємо нові елементи:
Тепер побудуємо “випадкові” вказівники у копіях – ми знаємо що кожен парний елемент у списку це копія.
І за останній прохі відновимо вказвники на наступний елемент в оригіналі і побудуємо вказвники в копії.
list_item* copy_list2(list_item *src) { list_item *headDst = NULL; for (list_item *curSrc = src, *nextSrc = NULL; curSrc; curSrc = nextSrc) { list_item *newDst = new list_item; if (!headDst) headDst = newDst; newDst->value = toupper(curSrc->value); nextSrc = newDst->next = curSrc->next; curSrc->next = newDst; } // build rnd pointers for copy for (list_item *curSrc = src; curSrc; curSrc = curSrc->next->next) { list_item *curDst = curSrc->next; curDst->rnd = curSrc->rnd->next; } // restore source next pointers and build copy next pointers for (list_item *curSrc = src; curSrc; curSrc = curSrc->next) { list_item *curDst = curSrc->next; curSrc->next = curDst->next; if (curDst->next) curDst->next = curDst->next->next; } return headDst; }