Ежедневный бит (е) 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.