Развернуть связный список

Развернуть в обратном порядке элементы в связном списке с позиции m до n. Сделать это за один проход.

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

Пример:

Дано: 1->2->3->4->5->NULL, m = 2, n = 4
Результат: 1->4->3->2->5->NULL

Идея решения 
Нам нужно помнить элемент curr (текущий) и pre (предыдущий).
prev.next=curr
curr.next=temp
prev>curr>temp 

Тогда, если мы хотим получить конфигурацию prev<curr<temp, то
curr.next = prev;
temp.next=curr.

Компилируемое решение

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
// фейковый элемент списка
        ListNode dummy = new ListNode(0);
        dummy.next = head; // фейк указывает на начало списка
        // проходим списка до позиции m
        ListNode cur1 = dummy;
        ListNode pre1 = null;
        for(int i=0;i<m;i++){
            pre1 = cur1;
            cur1 = cur1.next;
        }

// теперь в позиции pre1 у нас находится (m-1)-й элемент,
// в позиции cur1 у нас находится m-й элемент,
// который должен идти последним в развернутой цепочке от m до n
       
        //начиная с позиции m+1, разворачиваем список
        ListNode cur2 = cur1;
        ListNode pre2 = pre1;
        ListNode temp;
        for(int i=m;i<=n;i++){
            temp = cur2.next; // следующий элемент относительно cur2
            cur2.next = pre2; // разворот от cur2 к pre2
// продвигаемся далее по списку
            pre2 = cur2;
            cur2 = temp;
        }
       
        //соединяем цепочки 1-m, m-n, n-длина списка
// pre2 - содержит элемент, который был ранее на позиции n,
// на него должен указывать элемент в позиции m
        pre1.next = pre2;
// m-й элемент становится последним в цепочке m-n и должен указывать на n+1
        cur1.next = cur2;
       
        return dummy.next; // возвращаем голову исходного списка
    }
}

Анализ сложности

• Сложность по времени: $O(N)$, если список состоит из $N$ элементов. Мы рассматривает каждый элемент не более 1 раза (до n, а после n мы не просматриваем список вообще).
• Сложность по памяти: $O(1)$ у нас только константное число дополнительных указателей для конструирования финального результата.