# 4ms C++, linear, easy to understand, with thorough explanation

• ``````/* The idea:
* 1. break the list into 3 logical pieces, [1, m-1], [m, n] and [n+1, <end>]
* 2. run a standard reverse algorithm on the [m, n] sub-list
* 3. fix the wiring between the sub-lists
*/

class Solution {
public:
/* This is basically a standard linked-list reversal algorithm, with 2 extra arguments.
* What it does is starting from 'head' node, reverse the following 'count' nodes,
* store the 'next' node of our last element (which basically means the node at '[count+1]')
* as an output argument, then return the new head of our reversed sub-list (the node at '[count]').
*/
ListNode *reverseSubList(ListNode *head, int count, ListNode **next) {
return NULL;
}
if (count <= 1) {
}

ListNode *prev = NULL;

int i = 0;
while (curr && i<count) {
*next = curr->next;
curr->next = prev;
prev = curr;
curr = *next;
++i;
}

return prev;
}

ListNode *reverseBetween(ListNode *head, int m, int n) {
return NULL;
}
if (m == n) {
}

// Use pointer-to-pointer trick to re-wire the 'head' later.

// Loop until we reach the m-th element.
int i = 1;
while (curr && i<m) {
prev = &curr->next;
curr = curr->next;
++i;
}

// Call our sub-routine to reverse the sub-list in range [m, n].
ListNode *next = NULL;
curr = reverseSubList(curr, n-m+1, &next);

/* Now we have 3 logically separated lists, [1, m-1], [m, n] and [n+1, <end>].
* The [m, n] list has been reversed, but the wiring between the 3 lists
* are still broken, we need to fix that.
*
* The state of our variables:
* 'prev': points to a pointer, which in-turn points to our element at [m-1]
*          (if m==1, 'prev' points to the 'head' pointer of the entire list)
* 'curr': points to element at [n]
* 'next': points to element at [n+1]
*
* The fix is trivial:
* 1. Connect [m, n] list to [n+1, <end>] list.
*    The [m, n] list has been reversed, so the last element is [m], how do we
*    get access to this element? Note we have 'prev' point to element [m-1],
*    and the 'next' pointer of [m-1] never gets altered, so '[m-1]->next' still
*    points to [m]. And we also have 'next' points to [n+1], so this fix is easy.
* 2. Connect [1, m-1] list to [m, n] list.
*    We have 'prev' points to [m-1] and 'curr' points to [n], so this fix is easy too.
*/
(*prev)->next = next;
*prev = curr;

// if m==1, we have a new head stored in 'curr'
// if m>1, the head is unchanged
return m == 1 ? curr : head;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.