### leetcode Question 85: Reverse Linked List II

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULLm = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given mn satisfy the following condition:
1 ? m ? n ? length of list.
Analysis:

In this problem, do not think it too hard, reverse the linked list here is just reverse the value of node.
So the idea is to scan the linked list once, if not meet the reverse sublist, keep going, if reverse done(here the position is the middle of the sublist which needed to be reversed), return, because the latter list do not need any change. While in the sublist, for each element, (1)find the node to be swapped, (2) swap the values.
In the code below, note that,
(1) the stop condition is the middle of the reversed sublist (m+(n-m)/2)
(2) for each element in the sublist, the swapping element is the next (n-m-(i-m)*2) element.
e.g.
1-2-3-4-5-6-7-8-9-10-null
|                        |
m=2                  n=9
for 2, just get the next (n-m) element.

1-9-3-4-5-6-7-8-2-10-null
|                |
i=3          idx=8

next element 3, the swapping element is 8.

### Code(updated 201309):

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
for (int i=0;i<n-m;i++){
int k1=m+i;
int k2=n-i;
ListNode* p = h;
ListNode* q = h;
while (k1-1>0){p=p->next;k1--;}
while (k2-1>0){q=q->next;k2--;}
int tmp=p->val;
p->val=q->val;
q->val=tmp;
}
}
};


Code(old version):
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int i=1;
while (p!=NULL){
if (i>(m+int((n-m)/2))) {return head;}
if (i<m) {i++;p=p->next;}
else{
ListNode* q = p;
for (int j=0;j<(n-m-(i-m)*2);j++){
q=q->next;
}
int tmp = p->val;
p->val = q->val;
q->val=tmp;
i++;
p=p->next;
}
}
}
};


1. Code(updated 201309)还可以再优化一下，k1,k2每次都是从0跑到m+i, n-i, 如果先跑到m结点，从这儿开始算，两个游标每次跑的距离就会缩短m。

1. Yes, of course it can be done like you said (see my old version code), it is slight complex and need to be careful with the subscript. Thus, I post the newer version which is more straightforward.

Thanks for you comment!

2. 楼主你后来的那个版本通不过OJ....

1. Oh, thank you very much for your reply!
I've checked the code, it seems the line 15, m-n should be n-m.

3. Hey man, you can also do it by manipulating the pointers instead of swapping the values of each node. In fact, I prefer using the pointers, cause I think that's the original purpose of this problem.

4. Use one deque to store the ListNodes from m to n just for one pass, and then do the swap on the deque

5. This is not an efficient solution since you are going from the head to k1 and k2 position in each iteration.

6. A bit better:
class Solution {
public:
{
}
ListNode* reverseKGroup(ListNode* head, int k) {
int count=0;
if(sizenext;
cur->next=prev;
prev=cur;
cur=temp;
count++;
}

return prev;
}
};

7. Above code was for a different question.
The right solution is below:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n)
{
int count=0;
for(int i=0;inext;
}
first=prev;
slast=cur;
while(cur&&count<=(n-m))
{
temp=cur->next;
cur->next=prev;
prev=cur;
cur=temp;
count++;
}
ListNode *second=prev,*last=cur;
if(first!=NULL)
first->next=second;
slast->next=last;

if(m!=1)