Original website: https://www.lintcode.com/zh-cn/old/problem/reverse-linked-list-ii/#

#### 36. Flip list II

- describe
- note
- data
- evaluating

Discussion area

Flip the M node from the list to the part of the N node.

##### Matters needing attention

m，nMeet the length of 1 < < m < < < n > chain table

**Sample**
Give the list**1->2->3->4->5->null**， m = 2 And N = 4, return**1->4->3->2->5->null**

**Label**
linked list

Train of thought: through the while cycle, find the M node and the N node of the linked list. Then, through the three pointer to flip the middle node in m~n, the idea of turning in situ can refer to the flip list: http://www.cnblogs.com/Tang-tangt/P/8709167.html, the difference is that the initial value of the subsequent node is not NULL, but is equal to the original list m+1 node.

When the flipping is completed, it is judged whether the original list n-1 is empty, and if not empty, the linked list after the flip is mounted to the end of the N-1 node, and if it is empty, the flip list is returned directly.

ACCode：

/**
* Definition of singly-linked-list:
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: ListNode head is the head of the linked list
* @param m: An integer
* @param n: An integer
* @return: The head of the reversed ListNode
*/
ListNode * reverseBetween(ListNode * head, int m, int n) {
// write your code here
if (head==NULL)
{
return head;
}
ListNode * leftNodes=NULL;
ListNode *rightNodes=head;
ListNode * cur=head;
int i=1,j=i,count=0;
while(i<m)//Find the first m node of the original chain.
{
leftNodes=cur;
cur=cur->next;
i++;
}
while(j<n)//Find the first N node of the original chain.
{
rightNodes=rightNodes->next;
j++;
}
rightNodes=rightNodes->next;
ListNode * rePre=cur;
ListNode *renexN=rightNodes;//Part of the tail part should be mounted on the right part of the original list.
while(rePre!=rightNodes)//Flipping m~n nodes;
{
rePre=cur->next;
cur->next=renexN;
renexN=cur;
cur=rePre;
}
//renexNTo reverse part of the head, you should mount it to the left part of the original list.
if (leftNodes==NULL)
{
return renexN;
}
leftNodes->next=renexN;
return head;
}
};