Перевернуть связанный список с позиции m на n. Делайте это в один проход.

Примечание.1 ≤ m ≤ n ≤ длина списка.

Пример:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

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

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

  • Итеративное решение
ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (!head || !head->next || !m) {
        return head;
    }
    
    ListNode dummy(0), *it = &dummy;
    it->next = head;
    
    for (int i = 0; i < m - 1; ++i) {
        it = it->next;
    }
    
    ListNode* front = it;            
    ListNode* last = it->next; 
    
    ListNode* prev = NULL, *cur = it->next, *next = NULL;
    for (int i = m; i <= n; ++i) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    
    front->next = prev;
    last->next = cur;
    
    return dummy.next;
}

Разобьем эту задачу на несколько шагов. Во-первых, нам нужно найти mth узел. Затем, начиная с этой позиции, мы можем применить обычный алгоритм реверсирования итеративного связанного списка, пока не достигнем nth узла. Следовательно, диапазон между m и n меняется местами. Затем нам нужно соединить перевернутый список обратно в правильное положение. Поэтому нам также нужно отслеживать боковые узлы, то есть m-1th и n+1th node.

У нас может быть список шагов, чтобы сделать вещи более понятными:

  1. Найдите в списке узлы m-1th и mth.
  2. Начинайте реверсирование сmго узла на nй узел.
  3. Соедините старый mth узел с n+1th, а старый nth узел соедините после m-1th.

В частности, для первого шага обратите внимание, что, поскольку m может быть 1, заголовок списка может измениться. Таким образом, мы решили создать фиктивную голову впереди, чтобы создать фиктивный узел m-1th, а также сделать нашу реализацию более лаконичной. На втором этапе мы могли бы просто использовать стратегию с тремя указателями, чтобы перевернуть подсписок в этом диапазоне. Наконец, чтобы отслеживать узлы m-1th, themth, thenth и then+1th, обратите внимание, что когда мы итеративно переворачиваем неполный список, наш указатель prev остановится на новой голове, которая была nth узлом, а cur находится на n+1th. Таким образом, мы могли бы напрямую использовать их. Но для m-1th и mth мы можем потерять их след, как только начнется наше обращение. Поэтому перед началом операции реверсирования мы используем две переменные для хранения этих двух важных узлов. В моем коде front — m-1, а last — m. И, наконец, мы встраиваем перевернутый подсписок в позицию между front и cur.

Настало время простого примера:

Suppose that we have an input list:
1->2->3->4->5->NULL, m = 2, n = 4
Current List:       1->2->3->4->5->NULL
Initialization:     dummy -> 1, it = dummy
1st Step:           move it to 1
                    let front store 1    // the m-1th node
                    let last store 2     // the mth node
Current List:       dummy->1->2->3->4->5->NULL
Data Structure:     front = 1, last = 2
2nd Step:           reverse 2->3->4
Current List:       dummy->1, 2<-3<-4, 5->NULL
Data Structure:     prev = 4, cur = 5, next = 5
3rd Step:           let front point to prev
                    let last point to cur
Current List:       dummy->1->4->3->2->5->NULL
return dummy -> next = 1

Временная сложность: O(n) — нам нужно, по крайней мере, выполнить итерацию списка до nth узла, поэтому в случае, когда n равно размеру списка, мы должны пройти весь список.

Пространственная сложность: O(1) — мы почти не используем никаких вспомогательных структур данных, кроме нескольких указателей, поэтому пространственная сложность постоянна.