Ежедневный бит (е) C ++ # 119, Общая проблема на собеседовании: обратные k-группы в односвязном списке.

Сегодня мы рассмотрим распространенную задачу интервью: обратные k-группы в односвязном списке.

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

Вы должны изменять только порядок элементов, а не их значения.

Например, для списка {1,2,3,4,5} и k==2 вывод должен быть {2,1,4,3,5}.

Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/KPfWc4MKT.

Решение

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

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

Чтобы вызвать этот реверс несколько раз, нам нужно следить за парой вещей:

  • головка уже обработанной детали; это будет наш результат
  • хвост уже обработанной детали; здесь мы будем связывать каждый перевернутый раздел по мере повторения
  • головка необработанной части; как для итерации, так и для связывания хвоста обрабатываемой части
List::Node* reverse(List::Node *head, int64_t k) {
    List::Node *result = nullptr;
    List::Node *iter = head;

    for (int64_t i = 0; i < k; ++i)
        iter = std::exchange(iter->next, std::exchange(result, iter));
/* we want to put iter to the front of the list
   but we want the original value of result to be the new iter->next
   but we want the original value of iter->next to be the new iter
*/

    return result;
}

void reverse_groups(List &list, int64_t k) {
    List::Node *unprocessed_head = list.head;
    List::Node *processed_tail = nullptr;
    List::Node *result = nullptr;
    List::Node *iter = list.head;
    
    while (iter != nullptr) {
        // advanced by k elements
        int cnt = 0;
        iter = unprocessed_head;
        while (cnt < k && iter != nullptr) {
            iter = iter->next;
            ++cnt;
        }

        // if we have a full set of k elements
        if (cnt == k) {
            List::Node *processed_head = reverse(unprocessed_head, k);
            // initialize the result if this is the first group
            if (result == nullptr)
                result = processed_head;
            // if this isn't the first group, link the existing tail
            if (processed_tail != nullptr)
                processed_tail->next = processed_head;

            // what was head is now the tail of the reversed section
            processed_tail = unprocessed_head;
            // and iter is the new head
            unprocessed_head = iter;
        }
    }
    if (processed_tail != nullptr)
        processed_tail->next = unprocessed_head;
    list.head = result == nullptr ? unprocessed_head : result;
}

Откройте решение в Compiler Explorer.