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

Задача

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

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

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

Інвертувати список

Задача

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

Рішення

Проходимо по всьому списку і для кожного елементу спочатку зберігаємо адресу наступного, потім міняємо в поточному елементі адресу наступного елемента на адресу попереднього (спочатку адресу попереднього встановлено в 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;
}

Визначити чи зациклено список

Задача

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

Рішення

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

```
bool IsListLooped(list *l)
```
```
{
```
```
  list *slow = l, *fast = l;
```
```
  while (fast && fast->next)
```
```
  {
```
```
    fast = fast->next->next;
```
```
    slow = slow->next;
```
```
    if (fast == slow)
```
```
    {
```
```
      return true;
```
```
    }
```
```
  }
```
```
  return false;
```
```
}
```

* This source code was highlighted with Source Code Highlighter.

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

Складення чисел у списках

Задача

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

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

Рішення

```
list* AddLists(list *l1, list *l2)
```
```
{
```
```
  list *r = new list();
```
```
  int carry = 0, val = 0;
```

  for (; l1 || l2 || carry; l1 = l1->next, l2 = l2->next)

```
  {
```

    val = carry + l1 ? l1->val : 0 + l2 ? l2->val : 0;

```
    carry = val / 10;
```
```
    val %= 10;
```
```
    r->AddItem(val);
```
```
  }
```
```
  return r;
```
```
}
```

* This source code was highlighted with Source Code Highlighter.

Вилучити елемент зі списку за вказівником на нього

Задача

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

Рішення

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

```
void RemoveItem(list* item)
```
```
{
```
```
  if (!item ||!item->next) return;
```
```
  list *next = item->next;
```
```
  item->data = next->data;
```
```
  item->next = next->next;
```
```
}
```

* This source code was highlighted with Source Code Highlighter.

Зауваження

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

Повернути N-тий елемент з кінця списку

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

Всановлюємо вказівника р1 та р2 на початок списку.
Переміщуєма р2 на Н-1 позицій вперед.
Переміщуємо обидва вказівника на одну позицію вперед.
Якщо р2 не досягнув кінця списку то йдемо до кроку 3.
р1 містить результат.

list* NthToLastelement(list* head, int n)

```
{
```

  if (head == NULL || n < 1) return NULL;

```
  list *p1 = head, *p2 = head;
```

  for (int i = 0; i < n - 1 && p2; ++i, p2 = p2->next);

```
  if (p2 == NULL) retun NULL;
```

  for (; p2->next; p1 = p1->next, p2 = p2->next);

```
  return p1;
```
```
}
```

* This source code was highlighted with Source Code Highlighter.

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

Задача

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

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

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

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

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

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

void RemoveDups(list* head)
{
    if (head == NULL) return;
    list* prev = head;
    list* cur = prev->next;
    while (cur)
    {
	for (list *run = head; run != cur; run = run->next)
	{
  		if (run->data == cur->data)
		{
			// remove current item
			list *tmp = cur->next;
			prev->next = tmp;
			delete cur;
			cur = tmp;
                }
	}
		 
	if (run == cur)
	{
	    prev = cur;
	    cur = cur->next;
	}
    }
}

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