Обратный связанный список в группах заданного размера
Для заданного связанного списка напишите функцию, которая переворачивает каждые k узлов (где k — входные данные функции).
Пример:
Input: 1->2->3->4->5->6->7->8->NULL, K = 3
Output: 3->2->1->6->5->4->8->7->NULL
Input: 1->2->3->4->5->6->7->8->NULL, K = 5
Output: 5->4->3->2->1->8->7->6->NULL
Алгоритм : реверс (голова, k)
- Перевернуть первый подсписок размера k. При реверсировании следите за следующим узлом и предыдущим узлом. Пусть указатель на следующий узел будет next , а указатель на предыдущий узел будет prev . См. этот пост для обращения связанного списка.
- head->next = reverse(next, k) (рекурсивно вызывает остальную часть списка и связывает два подсписка)
- Вернуть предыдущее ( предыдущее становится новым началом списка (см. схемы итеративного метода в этом посте)
На изображении ниже показано, как работает функция реверса:
Ниже приведена реализация вышеуказанного подхода:
Анализ сложности:
- Временная сложность: O(n).
Обход списка выполняется только один раз и состоит из n элементов. - Вспомогательное пространство: O(n/k).
Для каждого связанного списка размера n, n/k или (n/k)+1 вызовов будет выполнено во время рекурсии.
Мы можем решить этот вопрос в O(1) Space Complexity.
Подход – 2 Оптимизация пространства – Итеративный
Для этого алгоритма необходимы следующие шаги:
- Создайте фиктивный узел и укажите его на начало ввода, т.е. dummy->next = head.
- Вычислите длину связанного списка, который занимает O(N) времени, где N — длина связанного списка.
- Инициализируйте трехуказатели prev, curr, next для обратного k элементов для каждой группы.
- Перебирать связанные списки до следующего!=NULL.
- Указывает curr на предыдущее->следующее и рядом с curr следующее.
- Затем, используя внутренний цикл for, переверните конкретную группу, выполнив следующие четыре шага:
- curr->next = next->next
- next->next = prev->next
- prev->next = next
- next = curr->next
7. Этот цикл for выполняется k-1 раз для всех групп, кроме последнего оставшегося элемента, для последнего оставшегося элемента он выполняется до оставшейся длины связанного списка — 1.
8. Уменьшить счетчик после цикла for на k count -= k, чтобы определить длину оставшегося связанного списка.
9. Измените предыдущую позицию на текущую, предыдущая = текущая.
Вот код для вышеуказанного алгоритма.
Анализ сложности
Сложность времени: O(N): цикл while занимает O(N/K) времени, а внутренний цикл for занимает O(K) времени. Итак, N/K * K = N. Следовательно, TC O(N)
Пространственная сложность: O(1): дополнительное пространство не используется.
Пожалуйста, пишите комментарии, если вы считаете приведенный выше код/алгоритм неверным или найдете другие способы решения той же проблемы.