Обратный связанный список в группах заданного размера

Для заданного связанного списка напишите функцию, которая переворачивает каждые 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 Оптимизация пространства – Итеративный

Для этого алгоритма необходимы следующие шаги:

1. Создайте фиктивный узел и укажите его на начало ввода, т.е. dummy->next = head.
2. Вычислите длину связанного списка, который занимает O(N) времени, где N — длина связанного списка.
3. Инициализируйте трехуказатели prev, curr, next для обратного k элементов для каждой группы.
4. Перебирать связанные списки до следующего!=NULL.
5. Указывает curr на предыдущее->следующее и рядом с curr следующее.
6. Затем, используя внутренний цикл 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): дополнительное пространство не используется.

Пожалуйста, пишите комментарии, если вы считаете приведенный выше код/алгоритм неверным или найдете другие способы решения той же проблемы.