Задача

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

image

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

Рішення 1

Спочатку створюємо копію кожного елемента і робимо наступні зміни:

  • вказівники на наступний і випадковий елемент у копії встановлюємо у значення випадкового вказвника оригінала
  • вказівник на випадковий елемент в оригіналі встановлюємо в адресу копії

image

На наступному проході (йдемо по оригінальному списку) встановлюємо “випадкові” вказівники в копіях.

image

На третьому проході відновлюємо “випадкові” вказівнику оригіналу з вказівників на наступний елемент копії, і одночасно встановлюємо вказівник на наступний елемнт в копіях.

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

Насправді нам не обов’язково двічі копіювати вказвники. Натомість кожен новий елемент-копію ми можемо додати у оригінальний список одразу за зкопійованим елементом.

Оригінал:

image

Додаємо нові елементи:

image

Тепер побудуємо “випадкові” вказівники у копіях – ми знаємо що кожен парний елемент у списку це копія.

image

І за останній прохі відновимо вказвники на наступний елемент в оригіналі і побудуємо вказвники в копії.

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;
}

 

Задача

Написати функцію яка розміщує елементи списку у зворотньому порядку.

Рішення

Проходимо по всьому списку і для кожного елементу спочатку зберігаємо адресу наступного, потім міняємо в поточному елементі адресу наступного елемента на адресу попереднього (спочатку адресу попереднього встановлено в NULL). Потім зберігаємо поточний елемент як попередній, а наступний як поточний.

list_item* reverse_list(list_item *l) { list_item *prev = NULL; for (list_item *cur = l ; cur; ) { list_item *next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }

Задача

Написати функцію копіювання списку.

Рішення

Йдемо по всим елементах оригінального списку і сворюємо копію для кожного з них. Головна деталь – треба зберігати вказівник на поереднь створений елемент щоб змінити в ньому вказівниек на наступний елемент.

struct list_item { int data; list_item *next; list_item(int d, list_item *n) : data(d), next(n) {} }; list_item* copy_list(list_item *list) { list_item *newList = NULL, *newInCopy = NULL, *prevInCopy = NULL; for (list_item *curInSource = list; curInSource; curInSource = curInSource->next) { newInCopy = new list_item(curInSource->data, NULL); if (!newList) newList = newInCopy; if (prevInCopy) prevInCopy->next = newInCopy; prevInCopy = newInCopy; } return newList; }

Задача дуже подібна до задачі про визначення того чи зациклено список.

Задача

Знайти елемент у списку на якому він зациклюється.

Рішення

З попередньої задачі знаємо як визначити що список зациклено.

Якщо є два вказівники по зацикленому списку один з яких переміщується по елементам вдвічі швидше за інший то зустрінуться вони в тому елементі з якого почали свій біг. Якщо тепер до першого кола додати k кроків то зустрінуться вони за k кроків до початку циклу. При цьому швидший зробить k+2(n-k) кроків, де n-кількість кроків у колі, а повільніший зробить n-k кроків. Тобто зустрінуться вони за k кроків від того елемента де починається цикл.

Після цього достатньо зробити k кроків щоб перейти до елементу в якому і зациклюється список.

list* FindListLoopBeginning(list *start)
{
  list *p1 = start, *p2 = start;
  
  while (p2 && p2->next)
  {
    p2 = p2->next->next;
    p1 = p1->next;
    
    if (p2 == p1) break;
  }
  
  if (!p2) return NULL;
  
  for (p1 = start; 
    p1->next != p2->next;
    p1 = p1->next, p2 = p2->next);
  
  return p2;
}

 

Задача

Дано список, треба визначити чи його зациклено, тобто чи вказує якийсь елемент на один з попередніх елементів.

Рішення

Якщо переміщувати два вказівники по елементах – один на кожен наступний за крок, а інший через елемент то шидкий вказівник або досягне кінця списку (у випадку коли список не зациклено), або їх значення колись співпадуть (тобто список зациклено).

    1. bool IsListLooped(list *l)
    2. {
    3.   list *slow = l, *fast = l;
    4.   while (fast && fast->next)
    5.   {
    6.     fast = fast->next->next;
    7.     slow = slow->next;
    8.     if (fast == slow)
    9.     {
    10.       return true;
    11.     }
    12.   }
    13.   return false;
    14. }

 

* This source code was highlighted with Source Code Highlighter.

Також дивись подібну задачу про знаходження елемента на якому зациклено список.

Задача

Є два списки в яких кожен елемент містить одну цифру числа. Числа зберігаються у зворотньому порядку, тобто йде найвагоміша цифра, останньою цифра що позначає одиниці. Треба написати функцію що складає ці списки і повертає новий список як результат складення.

Наприклад (9->3->5) + (8->7) повенно давати результат (1->0->2->2).

Рішення

    1. list* AddLists(list *l1, list *l2)
    2. {
    3.   list *r = new list();
    4.   int carry = 0, val = 0;
    5.   for (; l1 || l2 || carry; l1 = l1->next, l2 = l2->next)
    6.   {
    7.     val = carry + l1 ? l1->val : 0 + l2 ? l2->val : 0;
    8.     carry = val / 10;
    9.     val %= 10;
    10.     r->AddItem(val);
    11.   }
    12.   return r;
    13. }

 

* This source code was highlighted with Source Code Highlighter.

Задача

Написати функцію яка приймає вказівник на елемент і вилучає цей елемент зі списку.

Рішення

Скопіювати значення з наступного елемента у поточний, модифікувати вказівник на наступний елемент і видалити наступний елемент.

    1. void RemoveItem(list* item)
    2. {
    3.   if (!item ||!item->next) return;
    4.   list *next = item->next;
    5.   item->data = next->data;
    6.   item->next = next->next;
    7. }

 

* This source code was highlighted with Source Code Highlighter.

Зауваження

Алгоритм неможливо реалізувати для вказівника на останній елемент. В цьому випадку такий елемент можна позначити якимось чином щоб сигналізувати що його видалено.

Задачу можна розв’язати рекурсивно, але можна і за допомогою наступного простого алгоритму:

  1. Всановлюємо вказівника р1 та р2 на початок списку.
  2. Переміщуєма р2 на Н-1 позицій вперед.
  3. Переміщуємо обидва вказівника на одну позицію вперед.
  4. Якщо р2 не досягнув кінця списку то йдемо до кроку 3.
  5. р1 містить результат.
    1. list* NthToLastelement(list* head, int n)
    2. {
    3.   if (head == NULL || n < 1) return NULL;
    4.   list *p1 = head, *p2 = head;
    5.   for (int i = 0; i < n - 1 && p2; ++i, p2 = p2->next);
    6.   if (p2 == NULL) retun NULL;
    7.   for (; p2->next; p1 = p1->next, p2 = p2->next);
    8.   return p1;
    9. }

 

* This source code was highlighted with Source Code Highlighter.

Задача

Вилучити елементи що повторюються з невідсортованого списку. Як це можна зробити якщо нема пам’яті для додаткового буфера?

Рішення з додатковим буфером

Достатньо просто зберігати елементи в хеш-таблиці і прибирати дублікати якщо елемент з поточним значенням вже є у хешу.

Рішення без додаткового буфера

У цьому випадку можна працювати з двома вказівниками: одни вказує на поточний елемент що ми його перевіряємо, другий – для порівняння з усіма попкркдніми елементами.

В списку з одного елемента всі елементи унікальні, тому перевірку можна почати з другого елемента. Якщо другий елемент є унікальним то тепер у нас 2 елементи з якими можна порівнювати. І так далі…

    1. void RemoveDups(list* head)
    2. {
    3.    if (head == NULL) return;
    4.    list* prev = head;
    5.    list* cur = prev->next;
    6.    while (cur)
    7.    {
    8.      for (list *run = head; run != cur; run = run->next)
    9.     {
    10.       if (run->data == cur->data)
    11.       {
    12.         // remove current item
    13.         list *tmp = cur->next;
    14.         prev->next = tmp;
    15.         delete cur;
    16.         cur = tmp;
    17.       }
    18.     }
    19.     if (run == cur)
    20.     {
    21.       prev = cur;
    22.       cur = cur->next;
    23.     }
    24.   }
    25. }

 

* This source code was highlighted with Source Code Highlighter.

Також дивись Як прибрати символи-дублікати з С-рядка