Задачка: обратный(reverse) список

Давно хотел начать записывать задачки с собеседований и не только, но все как-то не получалось. Если трудно что-то начать, начни с самого легкого. Итак одна из простейших задач, тем не менее я умудрился запутаться на одном из собеседование - ревертнуть список.

Итак, входные данные: Дан односвязный список. Результат: получить обратный список (ревертнуть его).

Первое, что надо сделать - это не спешить ( чем я сам грешу ), а задать уточняющие вопросы, а именно:
  • Циклический ли это список ( последний элемент указывает на начало )? Если список циклический, то нужно воспринимать начальную вершину как конец списка.
  • Есть ли петли(loops) в этом списке? В том смысле, что конец ссылается на середину списка. В этом случаем надо запоминать вершины которые проедены ( можно по адресу и в массив ) и прежде чем делать следующею итерацию, смотреть не посещали ли эту вершину. Если да то, значит мы пришли к концу. Хотя что за реверс списка это будет не понятно.
  • Фиксированное число элементов в этом списке? ( реальный случай ) Если число фиксированное и оно не большое(3-5), то значит смотрели на внимательность. Тут все просто надо руками ревертнуть эти объекты.
  • Нужно ли сохранять оригинальный список? Тогда нельзя изменять оригинальный список, а создавать новый и возвращать указатель на новый.

Если на все эти вопросы ответ - нет, то только тогда можно приступать к разработке алгоритма.

Я, как правило, забывал спрашивать эти вопросы, так как торопишься, нервничаешь и иногда еще и говоришь на иностранном языке, что точно не дает мозгу спокойно расслабиться и подумать. На некоторые из этих я лично нарывался, пару я придумал из темы, а какие подвохи можно придумать.

Ладно, сам алгоритм прост до безобразия:

typedef struct Item {
  int value;
  struct Item* next;
} Item;

Item *list_revert(Item *head) {
  Item *tmp, *prev = NULL;
  if ( NULL == head )
    return NULL;
  while ( head->next ) {
    tmp = head->next; // 1. Save next
    head->next = prev; // 2. Modify previous
    prev = head; // 3. Make previous as head
    head = tmp; // 4. Move to next node
  }
  head->next = prev;
  return head;
}

Подробно можно посмотреть в revert_list.c.

Вот и все, но я даже на этом умудрился затупить на одном из собеседований - так что не расслабляйтесь, сглупить можно всегда :) .

Совсем забыл, я люблю смотреть, а как эта штука реализована в STL. Сразу хочу сказать, что в STL много вариантов reverse, но нам нужно только односвязный (forward) список:

inline _Slist_node_base*
__slist_reverse(_Slist_node_base* __node)
{
   // __node is never null
  _Slist_node_base* __result = __node;
  __node = __node->_M_next;
  __result->_M_next = 0;
  while(__node)
    {
      _Slist_node_base* __next = __node->_M_next;
      __node->_M_next = __result;
      __result = __node;
      __node = __next;
    }
  return __result;
}

Сложность алгоритма линейная O(n).

Вот теперь, пожалуй, и все.