# 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->NULL, m = 2 and n = 4,

> return 1->4->3->2->5->NULL.

> Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

```c++
//保存p3
n = p2->next;
//将p3的next挂载到p2后面
p2->next = p3->next;
//将p3挂载到p1的后面
p1->next = p3;
//将p2挂载到p3得后面
p3->next = p2;
```

```c++
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
if(!head) {
return head;
}

ListNode dummy(0);
dummy.next = head;

ListNode* p = &dummy;
for(int i = 1; i < m; i++) {
p = p->next;
}

//p此时就是pm的前驱节点
ListNode* pm = p->next;

for(int i = m; i < n; i++) {
ListNode* n = pm->next;
pm->next = n->next;
n->next = p->next;
p->next = n;
}

return dummy.next;
}
};
```

# Reverse Nodes in k-Group

> Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

> If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

> You may not alter the values in the nodes, only nodes itself may be changed.

> Only constant memory is allowed.

> For example,
> Given this linked list: 1->2->3->4->5

> For k = 2, you should return: 2->1->4->3->5

> For k = 3, you should return: 3->2->1->4->5

```c++
ListNode *reverseKGroup(ListNode *head, int k) {
if(k <= 1 || !head) {
return head;
}

ListNode dummy(0);
dummy.next = head;
ListNode* p = &dummy;
ListNode* prev = &dummy;

while(p) {
prev = p;
for(int i = 0; i < k; i++){
p = p->next;
if(!p) {
//到这里已经不够k个没法翻转了
return dummy.next;
}
}

p = reverse(prev, p->next);
}

return dummy.next;
}

ListNode* reverse(ListNode* prev, ListNode* end) {
ListNode* p = prev->next;

while(p->next != end) {
ListNode* n = p->next;
p->next = n->next;
n->next = prev->next;
prev->next = n;
}

//这里我们会返回最后一个节点，作为下一组的前驱节点
return p;
}
```