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

The Blind Swordsman: Zatoichi (2003)

Особисто у мене склалося таке враження що Такєши Кітано у цьому фільмі жорстоко стьобає з голівудських бойовиків.

Особливо це видно у фінальних сценах, де навіть незацікавлені у кіно люди мають відчути що “щось тут не так” Smile

І тим не менше це кльовий, хоча і мало правдоподібний екшн.

http://www.imdb.com/title/tt0363226/

[youtube=http://www.youtube.com/watch?v=_3WNmW5X8dI&fs=1&hl=en_US]

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

Задача

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

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

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

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

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

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

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