Posted by

Oleksandr Golovatyi on Березень 16, 2012

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

Задача

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

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

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

Posted by

Oleksandr Golovatyi on Лютий 24, 2012

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

Задача

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

Рішення

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

Posted by

Oleksandr Golovatyi on Лютий 24, 2012

Копіювання списку

Задача

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

Рішення

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

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

Posted by

Oleksandr Golovatyi on Січень 21, 2011

Знайти елемент на якому зациклено список

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

Задача

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

Рішення

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

Якщо є два вказівники по зацикленому списку один з яких переміщується по елементам вдвічі швидше за інший то зустрінуться вони в тому елементі з якого почали свій біг. Якщо тепер до першого кола додати 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;
}

Posted by

Oleksandr Golovatyi on Січень 21, 2011

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

Задача

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

Рішення

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

```
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.

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

Posted by

Oleksandr Golovatyi on Січень 4, 2011

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

Задача

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

Наприклад (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.

Posted by

Oleksandr Golovatyi on Грудень 29, 2010

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

Задача

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

Рішення

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

```
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.

Зауваження

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

Posted by

Oleksandr Golovatyi on Грудень 27, 2010

Повернути 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.

Posted by

Oleksandr Golovatyi on Грудень 27, 2010

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

Задача

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

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

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

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

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

В списку з одного елемента всі елементи унікальні, тому перевірку можна почати з другого елемента. Якщо другий елемент є унікальним то тепер у нас 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;
```
```
    }
```
```
  }
```
```
}
```

* This source code was highlighted with Source Code Highlighter.

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

Пн	Вт	Ср	Чт	Пт	Сб	Нд
« Сер
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

Category Archives

Задача

Рішення 1

Рішення 2

Задача

Рішення

Задача

Рішення

Задача

Рішення

Задача

Рішення

Задача

Рішення

Задача

Рішення

Зауваження

Задача

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

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