## 题目描述

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

**Note: **1 ≤ mn ≤ length of list.

Example:

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

## 思路

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

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

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

``````class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode *dummy = new ListNode(-1), *pre = dummy;
for (int i = 0; i < m - 1; ++i) pre = pre->next;
ListNode *cur = pre->next;
for (int i = m; i < n; ++i) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = pre->next;
pre->next = t;
}
return dummy->next;
}
};
``````

## 关键点解析

• 链表的基本操作（交换）
• 虚拟节点dummy 简化操作
• 考虑特殊情况 m 是 1 或者 n是链表长度的情况
• 用四个变量记录特殊节点， 然后操作这四个节点使之按照一定方式连接即可。
``````    let midStartNode = null;
let preMidStartNode = null;
let midEndNode = null;
let postMidEndNode = null;
``````
• 注意更新current和pre的位置， 否则有可能出现溢出

## 代码

JavaScript Code:

``````/*
* @lc app=leetcode id=92 lang=javascript
*
* [92] Reverse Linked List II
*
*
* algorithms
* Medium (34.13%)
* Total Accepted:    182.3K
* Total Submissions: 532.8K
* Testcase Example:  '[1,2,3,4,5]\n2\n4'
*
* 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
*
*
*/
/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
var reverseBetween = function(head, m, n) {
// 虚拟节点，简化操作
const dummyHead = {
}

let current = dummyHead.next; // 当前遍历的节点
let pre = current; // 因为要反转，因此我们需要记住前一个节点
let index = 0; // 链表索引，用来判断是否是特殊位置（头尾位置）

// 上面提到的四个特殊节点
let midStartNode = null;
let preMidStartNode = null;
let midEndNode = null;
let postMidEndNode = null;

while(current) {
const next = current.next;
index++;

// 对 (m - n) 范围内的节点进行反转
if (index > m && index <= n) {
current.next = pre;
}

// 下面四个if都是边界, 用于更新四个特殊节点的值
if (index === m - 1) {
preMidStartNode = current;
}
if (index === m) {
midStartNode = current;
}

if (index === n + 1) {
postMidEndNode = current;
}

if (index === n) {
midEndNode = current;;
}

pre = current;

current = next;
}

// 两个链表合并起来
(preMidStartNode || dummyHead).next = midEndNode; // 特殊情况需要考虑
midStartNode.next = postMidEndNode;

};

``````

C++ Code:

``````/**
* 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 s, int e) {
if (s == e) return head;
ListNode* prev = nullptr;
auto cur = head;
for (int i = 1; i < s; ++i) {
prev = cur;
cur = cur->next;
}
// 此时各指针指向：
// x -> x -> x -> x  -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> x -> x -> x ->
// ^head          ^prev ^cur
ListNode* p = nullptr;
auto c = cur;
auto tail = c;
ListNode* n = nullptr;
for (int i = s; i <= e; ++i) {
n = c->next;
c->next = p;
p = c;
c = n;
}
// 此时各指针指向：
// x -> x -> x -> x     8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1     x -> x -> x ->
// ^head          ^prev ^p                                 ^cur  ^c
//                                                         ^tail
if (prev != nullptr) { // 若指向前一个节点的指针不为空，则说明s在链表中间（不是头节点）
prev->next = p;
cur->next = c;
} else {
if (tail != nullptr) tail->next = c;
return p;
}
}
};
``````

Python Code:

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
"""采用先翻转中间部分，之后与不变的前后部分拼接的思路"""
# 处理特殊情况
if m == n:

# 例行性的先放一个开始节点，方便操作
first = ListNode(0)

# 通过以下两个节点记录拼接点
before_m = first  # 原链表m前的部分
after_n = None  # 原链表n后的部分

# 通过以下两个节点记录翻转后的链表
between_mn_end = None

index = 0
cur_node = first
while index < n:
index += 1
cur_node = cur_node.next
if index == m - 1:
before_m = cur_node
elif index == m:
between_mn_end = ListNode(cur_node.val)
elif index > m:
if index == n:
after_n = cur_node.next

# 进行拼接
between_mn_end.next = after_n