BiruLyu
8/2/2017 - 9:52 PM

## 92. Reverse Linked List II(#).java

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || m >= n) {
}

ListNode sentinel = new ListNode(-1);
ListNode node = sentinel;

// move the "node" pointer in front of the m-th node
for (int i = 1; i < m; ++i) {
node = node.next;
}

// reverse nodes
ListNode curr = node.next;
for (int i = m; i < n; ++i) {
ListNode temp = node.next;
node.next = curr.next;
curr.next = curr.next.next;
node.next.next = temp;
}

return sentinel.next;
}
}``````
``````public ListNode reverseBetween(ListNode head, int m, int n) {
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;

}``````