# 92. Reverse Linked List II 反转链表 II

@TOC

## # 题目描述

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

## # 解题方法

### # 迭代

Python代码如下：

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type m: int
:type n: int
:rtype: ListNode
"""
count = 1
root = ListNode(0)
pre = root
while pre.next and count < m:
pre = pre.next
count += 1
if count < m:
mNode = pre.next
curr = mNode.next
while curr and count < n:
next = curr.next
curr.next = pre.next
pre.next = curr
mNode.next = next
curr = next
count += 1
return root.next

C++代码如下：

/**
* 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 pos = 1;
ListNode* dummy = new ListNode(0);
ListNode* pre = dummy;
while (cur && pos < m) {
pre = pre->next;
cur = cur->next;
pos ++;
}
ListNode* tailNode = cur;
while (cur && pos <= n) {
ListNode* nxt = cur->next;
cur->next = pre->next;
pre->next = cur;
tailNode->next = nxt;
cur = nxt;
pos ++;
}
return dummy->next;
}
};

### # 递归

1. 那么，如果m==n，则不用翻转，直接返回原来的头即可。
2. 如果m!=1的时候，该节点不用翻转，继续翻转后面的节点。
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (m == n)
if (m != 1) {