• Time:O(n)
• Space:O(n)

C++

``````class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (left == 1)

}

private:
ListNode* reverseN(ListNode* head, int n) {
if (n == 1)

}
};
``````

JAVA

``````class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == 1)

}

private ListNode reverseN(ListNode head, int n) {
if (n == 1)

}
}
``````

Python

``````class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if left == 1:

def reverseN(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if n == 1:

``````

• Time:O(n)
• Space:O(1)

C++

``````class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (!head || m == n)

ListNode* prev = &dummy;

for (int i = 0; i < m - 1; ++i)
prev = prev->next;  // point to the node before the sublist [m, n]

ListNode* tail = prev->next;  // will be the tail of the sublist [m, n]

// reverse the sublist [m, n] one by one
for (int i = 0; i < n - m; ++i) {
ListNode* cache = tail->next;
tail->next = cache->next;
cache->next = prev->next;
prev->next = cache;
}

return dummy.next;
}
};
``````

JAVA

``````class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || m == n)

ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;

for (int i = 0; i < m - 1; ++i)
prev = prev.next; // point to the node before the sublist [m, n]

ListNode tail = prev.next; // will be the tail of the sublist [m, n]

// reverse the sublist [m, n] one by one
for (int i = 0; i < n - m; ++i) {
ListNode cache = tail.next;
tail.next = cache.next;
cache.next = prev.next;
prev.next = cache;
}

return dummy.next;
}
}
``````

Python

``````class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head and m == n:

prev = dummy

for _ in range(m - 1):
prev = prev.next  # point to the node before the sublist [m, n]

tail = prev.next  # will be the tail of the sublist [m, n]

# reverse the sublist [m, n] one by one
for _ in range(n - m):
cache = tail.next
tail.next = cache.next
cache.next = prev.next
prev.next = cache

return dummy.next
``````