Для связанного списка переверните узлы связанного списка k за раз и верните его измененный список.

k - положительное целое число, которое меньше или равно длине связанного списка. Если количество узлов не кратно k, то оставленные узлы в конце должны оставаться такими, как есть.

Пример:

Учитывая этот связанный список: 1->2->3->4->5

Для k = 2 вы должны вернуть: 2->1->4->3->5

Для k = 3 вы должны вернуть: 3->2->1->4->5

Примечание.

Допускается только постоянная дополнительная память.

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

Эта проблема требует от нас перевернуть сегмент связанного списка с k узлами за раз, что очень похоже на проблему, которую мы решали ранее. Напомним, что мы столкнулись с проблемой, которая заставила нас перевернуть подсписок из m -го узла и n -го узла в списке. А этот - просто проделывать такую ​​операцию несколько раз. Мы также представим как итерационные, так и рекурсивные решения этого вопроса.

  • Итерационное решение

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

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

Итак, давайте составим список того, что нам нужно сделать, чтобы полностью перевернуть весь список k узлов за раз:

  1. Обратите внимание, что если последующий список из заголовка не содержит узлов k, ничего менять не нужно. Поэтому нам определенно нужно проверить, остались ли еще k узлов. Если есть, продолжаем. В противном случае алгоритм может остановиться.
  2. Поменяйте местами следующие k последовательных узлов. Тем временем отслеживайте информацию о четырех узлах: узел перед головой, голова, хвост и узел после хвоста.
  3. Наконец, верните перевернутый подсписок в правильное положение, между узлом перед головой (бывшая голова) и узлом после хвоста (бывший хвост).
  4. Переход к следующему подсписку назад.

Итак, после того как мы перечислим все, что нам нужно сделать, логика станет довольно ясной, не так ли? Теперь давайте посмотрим на реализацию.

ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head || !head->next || k <= 1) {
        return head;
    }
    
    ListNode dummy(0), *prev = &dummy;
    prev->next = head;
    
    while (true) {
        ListNode* it = prev->next;
        int count = 0;
        while (it) {
            ++count;
            if (count == k) {
                break;
            }
            it = it->next;
        }
        if (count < k) {
            break;
        }
        
        ListNode* nextPrev = prev->next;
        
        ListNode* prev2 = NULL, *cur = prev->next, *next = NULL;
        for (int i = 0; i < k; ++i) {
            next = cur->next;
            cur->next = prev2;
            prev2 = cur;
            cur = next;
        }
        
        prev->next = prev2;
        nextPrev->next = cur;
        
        prev = nextPrev;
    }
    
    return dummy.next;
}

В плане реализации код на самом деле не так прост, как алгоритм. Это в основном потому, что есть множество указателей, которые нам нужно переназначить и перенаправить.

Сначала, как обычно, проверим крайние случаи. Если список ввода пуст или содержит только один элемент, нам определенно не нужно ничего делать с ним. Кроме того, если k меньше или равно 1, входной список также не нужно изменять. Затем мы используем трюк с фиктивной головой, чтобы упростить наш код. Почему это помогает в этом случае? Очевидный ответ заключается в том, что заголовок входного списка может измениться, и если мы будем следить за заголовком, пока выполняем другую нашу логику, алгоритм может стать очень трудноразрешимым. Кроме того, обратите внимание, что нам нужно перевернуть подсписок, содержащий head. Если мы хотим перевернуть подсписок, эти четыре критических узла в соединениях очень важны. Если у нас здесь нет фиктивного узла, наша голова фактически не имеет прецедентного узла, поэтому наш алгоритм может стать трудным для кодирования.

Затем перейдем к итерации и переворачиваем k узлов за раз. На каждой итерации первое, что нам нужно проверить, это наличие в списке хотя бы k последующих узлов. Таким образом, нельзя избежать линейного сканирования не более чем k узлов. Это может показаться немного дорогостоящим, но при первом сканировании мы можем сделать гораздо больше. Во-первых, если мы обнаружим, что ход доходит до конца списка, мы можем напрямую вернуть текущий результат, поскольку больше не требуется разворачивания. В противном случае нам нужно продолжить работу. Обратите внимание, что нам также необходимо отслеживать эти четыре основных узла подключения. Какие из них мы уже можем получить и хранить в данный момент? Ясно, что теперь мы можем сохранить предыдущий узел головного prev и головного узла prev->next. И после первой итерации мы также можем получить последние два узла, но в моей реализации я не сохранил их заранее, потому что на нашем шаге разворота узел cur достигнет следующего узла последнего узла, верно? И prev2 - это старый хвост и новая голова. Таким образом, нам не обязательно хранить их заранее.

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

Рассмотрим простой пример:

Suppose that we are given a list:
1->2->3->4->5->NULL, k = 2
Initialization:     dummy -> 1, prev = dummy
Current List:       dummy->1->2->3->4->5->NULL
First Iteration:    let it point to 1
                    increase count for 1, becomes 1
                    let it point to 2
                    increase count for 1, becomes 2
                    there are at least 2 nodes left
                    set nextPrev to 1
                    reverse from 1 to 2
                    let 1 point to NULL
                    let 2 point to 1
                    prev2 is 2
                    cur is 3
                    let prev (dummy) point to prev2 (2)
                    let nextPrev (1) point to cur (3)
                    move prev (dummy) to nextPrev (1)
Current List:       dummy->2->1->3->4->5->NULL
Second Iteration:   let it point to 3
                    increase count for 1, becomes 1
                    let it point to 4
                    increase count for 1, becomes 2
                    there are at least 2 nodes left
                    set nextPrev to 3
                    reverse from 3 to 4
                    let 3 point to NULL
                    let 4 point to 3
                    prev2 is 4
                    cur is 5
                    let prev (1) point to prev2 (4)
                    let nextPrev (3) point to cur (5)
                    move prev (1) to nextPrev (3)
Current List:       dummy->2->1->4->3->5->NULL
Second Iteration:   let it point to 5
                    increment count for 1, becomes 1
                    let it point to NULL
                    there is only 1 node left
                    halt
                    
return dummy.next = 2

Сложность времени: O (n). Обычно нам нужно дважды перебирать список. Во-первых, на каждой итерации мы должны сначала посмотреть вперед, чтобы проверить, осталось ли k узлов. Если есть, нам нужно их перевернуть, что является еще одним линейным сканированием. Таким образом, общая временная сложность остается линейной.

Сложность пространства: O (1) - единственной основной структурой данных, которую мы использовали в этой реализации, по-прежнему являются указатели, поэтому затраты на пространство постоянны.

  • Рекурсивное решение

Мы прошли итеративное решение. Теперь настала очередь и для рекурсии.

Первоначально нам все еще нужно подумать о том, как мы можем разбить большую проблему на более мелкие. Итак, в этой задаче нас просят перевернуть k узлов за раз, поэтому мы собираемся перевернуть сначала k узлов, а затем второй набор k узлов и так далее, пока мы не дойдем до конца списка. Итак, на каждой итерации мы собираемся сделать k- обратное время и перейти к следующему раунду. Таким образом, если мы можем сделать это обращение в текущем вызове функции, а затем каким-то образом напрямую получить обратный результат для последующего связанного списка и правильно их соединить, проблема должна быть решена. Обратите внимание, что «напрямую получить обратный результат для последующего связанного списка» требует от нас использования той же стратегии для обратного преобразования меньшего списка, так что это подзадача, которую мы ищем.

Теперь давайте поговорим о конкретном рекурсивном правиле:

  1. Базовый случай: в списке меньше k узлов.
  2. Рекурсивные правила: 1) Рекурсивно перевернуть список, начиная с k + 1- -го узла. 2) Переверните узлы k, начиная с текущего заголовка, и подключите новый перевернутый подсписок к результату публикации.

Что касается базового случая, я бы сказал, что это не так интуитивно понятно, поскольку у многих вопросов есть базовые варианты, которые можно решить за постоянное время. Но здесь обратите внимание, что для определения, попадает ли вызов функции в базовый вариант или нет, требуется как минимум сканирование узлов k. Но мы также можем сделать несколько вещей в этом первом сканировании, то есть получить начальный узел для следующего рекурсивного вызова, которым должен быть k + 1 -й узел.

Затем мы можем сделать следующий рекурсивный вызов, чтобы перевернуть последующий список, и в текущей функции мы выполним локальное реверсирование, а затем подключим новый перевернутый список к результату публикации, который мы получаем из подзадачи. Тогда все готово.

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* it = head;
    int count = 0;
    while (it) {
        ++count;
        if (count == k) {
            break;
        }
        it = it->next;
    }
    if (count < k)
        return head;
    
    ListNode* post = reverseKGroup(it->next, k);
    
    ListNode* prev = NULL, *cur = head, *next = NULL;
    for (int i = 0; i < k; ++i) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    
    head->next = post;
    
    return prev;
}

Структура кода очень похожа на итеративное решение. Нам просто нужно позволить последующим рекурсивным вызовам обрабатывать все эти подзадачи. Наша цель в каждом вызове функции - просто перевернуть текущие узлы k, начиная с заголовка ввода.

Опять же, давайте попробуем пример:

Suppose that we have an input list:
1->2->3->4->5->NULL, k = 2
Current List:           1->2->3->4->5->NULL
In Main Function:       call reverseKGroup(1)
Current List:           1->2->3->4->5->NULL
In reverseKGroup(1):    let it point to 1
                        increase count for 1, becomes 1
                        let it point to 2
                        increase count for 1, becomes 2
                        there are at least 2 nodes
                        call reverseKGroup(3)
Current List:           1->2->3->4->5->NULL
In reverseKGroup(3):    let it point to 3
                        increase count for 1, becomes 1
                        let it point to 4
                        increase count for 1, becomes 2
                        there are at least 2 nodes
                        call reverseKGroup(5)
Current List:           1->2->3->4->5->NULL
In reverseKGroup(5):    let it point to 5
                        increase count for 1, becomes 1
                        there is only 1 node left
                        hit base case
                        return 5
Current List:           1->2->3->4->5->NULL
In reverseKGroup(3):    get 5 from reverseKGroup(5)
                        
                        reverse from 3 to 4
                        let 3 point to 5
                        return 4
Current List:           1->2->4->3->5->NULL
In reverseKGroup(1):    get 4 from reverseKGroup(3)
                        reverse from 1 to 2
                        
                        let 1 point to 3
                        return 2
Current List:           2->1->4->3->5->NULL
In Main Function:       get 2

Сложность времени: O (n) - то же, что и итерационное решение. Это связано с тем, что при каждом вызове функции нам нужно сначала проверить, осталось ли k узлов, начиная с заголовка ввода, и если они есть, мы должны их отменить. Таким образом, по-прежнему необходимы два линейных сканирования.

Сложность пространства: O (n / k). При рекурсии необходимо учитывать стоимость стеков вызовов. Предполагается, что для каждых k узлов мы должны рекурсивно вызывать функцию только один раз. Таким образом, общее количество рекурсивных вызовов составляет n / k. Внутри каждой функции мы по-прежнему используем только пару указателей в этом алгоритме, поэтому они имеют постоянную стоимость. Таким образом, общая сложность пространства составляет O (n / k) .