Скопіювати список з випадковими вказівниками

Задача

Є однозв’язний список кожен елемент якого крім даних та вказівника на наступний елемент також містить вказівник на будь-який елемент з цього ж списку. Треба написати функцію “глибокого” копіювання такого списку – так щоб у копії випадкові вказівники вказували на ті ж елементи що і в оригіналі.

Копіювання повинно виконуватися за лінійний час без виділення додаткової пам’яті.

Рішення 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;
}

Залишити відповідь

Зайти з допомогою: