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

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

Задача

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

Рішення

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

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

Зауваження

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

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

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

  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 елементи з якими можна порівнювати. І так далі…

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

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

Чи є один рядок здвинутим іншим рядком

Задача

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

Рішення

Якщо додати до першого рядка його копію то другий рядок має бути підрядком сумарного рядка, якщо звісно це ті ж самі рядки.

 
bool IsRotation(char *s1, char *s2)
{
    bool result = false;
    int l1 = strlen(s1), l2 = strlen(s2);
    if (l1 == l2 && l1 > 0)
    {
        char *s = new char[l1 * 2 + 1];

        strcpy(s, s1); // concat strings
        strcpy(s + l1, s1)

        result = strstr(s, s2) != NULL;
        delete []s;
    }

    return result;
}

Встановлення колонок і рядків в 0

Задача

Для масиву розміром MxN якщо будь-який елемент дорівнює 0 встановити всі елементи його рядка і колонки в 0.

Рішення

Головна проблема полягає в тому щоб при встановленні елементів у 0 не враховувати їх при подальшому пошуку. Інакше змінені елементи будуть можуть бути просканованим пізніше і призведуть до встановлення в 0 нових елементів.
Найпростішим рішенням буде створити копію матриці в якій і міняти елементи, а сканування проводити лише на оригінальній матриці.
Але насправді немає необхідності  у всих MxN елементах – нам достатньо лише знати в яких рядках та стовпцях зустрівся хоча б один 0.
    1. void SetZeroes(int* a, int n, int m)
    2. {
    3.     int *row = new int[m];
    4.     int *col = new int[n];
    5.     // scan elements
    6.     for (int i = 0; i < n; ++i)
    7.     {
    8.         for (int j = 0; j < m; ++j)
    9.         {
    10.             if (a[i][j] == 0)
    11.             {
    12.                 row[i] = 1;
    13.                 col[j] = 1;
    14.             }
    15.         }
    16.     }
    17.     // set elements
    18.     for (int i = 0; i < n; ++i)
    19.     {
    20.         for (int j = 0; j < m; ++j)
    21.         {
    22.             if (row[i] == 1 || col[j] == 1)
    23.             {
    24.                 a[i][j] = 0;
    25.             }
    26.         }
    27.     }
    28.     delete [] row;
    29.     delete [] col;
    30. }

* This source code was highlighted with Source Code Highlighter.