# Simple Java solution with clear explanation

• Simply just reverse the list along the way using 4 pointers: dummy, pre, start, then

``````public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
for(int i = 0; i<m-1; i++) pre = pre.next;

ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed
ListNode then = start.next; // a pointer to a node that will be reversed

// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
// dummy-> 1 -> 2 -> 3 -> 4 -> 5

for(int i=0; i<n-m; i++)
{
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
}

// first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
// second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)

return dummy.next;

}``````

• @AS11
r u swapping start and then everytime

• Oh man... This is so clean.. My code takes like 60 lines...

• Can we use dummy node if it requires in-place?

• @CharlesLee "in place" is a controversial subject. In most resources, including LeetCode, it refers constant space, O(1); however some resources use it, unfortunately, as O( log n ). This solution above is O(1) space, because the amount of extra used memory is constant, even if the problem size changes (here, the length of ListNode chain). Therefore, it works in place.

For reference, see the first 2 paragraphs of this Wiki page:
https://en.wikipedia.org/wiki/In-place_algorithm

• @ozzyy Yes, you are right. "An in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables"

• Is the logic of your code moving a node before the node of position m for every iteration?

• it's so 666666

• Genius solution with a new LIstNode pointing to the head!

• @ardyadipta Absolutely marvellous

• 6666666666666666666

• 本当に6666666666

• Two phase Java solution:
First while loop moves cur to index = m;
Second while loop conduct a normal LinkedList reverse.

``````   public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
ListNode dummy = new ListNode(0);
ListNode pre = dummy, cur = head;
int k = 1;
while(cur.next != null && k != m){
cur = cur.next;
pre = pre.next;
k++;
}

while(cur.next != null && k != n){
ListNode preNext = pre.next;
pre.next = cur.next;
ListNode next = cur.next;
cur.next = next.next;
next.next = preNext;
k++;
}

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

• @AS11 From my understanding, it basically does two things:

1. start, which records mNode, bubbles up step by step to where the nNode originally is; start node never change, it is always the mNode;
2. then, which is always the next node of start (obviously it changes every time), is repeatedly being put to the next position of the pre node ( pre node doesn't change either), so that nodes between pre (not include) and start (include) is always in descending order.

Hope it helps!

• I think it is smart.

• I think the logic is:
Always insert "then" to the front (pre.next).

Actually it is the same with reverse linked list.

• if(head == null) return null;
ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
for(int i = 0; i<m-1; i++) pre = pre.next;

``````ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed
ListNode then = start.next; // a pointer to a node that will be reversed

// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
// dummy-> 1 -> 2 -> 3 -> 4 -> 5

for(int i=0; i<n-m; i++)
{
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
}

// first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
// second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)

return dummy.next;
``````

What's the point of the dummy node?

• How did you come up with this code. Mine is like 50 lines long and it still can't deal with all the corner cases. Every time I did the linked list problems, I always got wrong answers at my first few submissions because my solution can only deal with normal cases. And those special cases like m == n, m == 1 will always crush my program. I just can't come up with such elegant code without much hardcoding...

• Very clean code! U R such a genius! :-)

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