Reverse Linked List II
最后更新于：2022-04-02 01:10:35
# Reverse Linked List II
### Source
- leetcode: [Reverse Linked List II | LeetCode OJ](https://leetcode.com/problems/reverse-linked-list-ii/)
- lintcode: [(36) Reverse Linked List II](http://www.lintcode.com/en/problem/reverse-linked-list-ii/)
### Problem
Reverse a linked list from position m to n.
#### Example
Given **1->2->3->4->5->NULL**, m = 2 and n = 4, return1->4->3->2->5->NULL.
#### Note
Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
#### Challenge
Reverse it in-place and in one-pass
### 题解
此题在上题的基础上加了位置要求，只翻转指定区域的链表。由于链表头节点不确定，祭出我们的dummy杀器。此题边界条件处理特别tricky，需要特别注意。
1. 由于只翻转指定区域，分析受影响的区域为第m-1个和第n+1个节点
1. 找到第m个节点，使用for循环n-m次，使用上题中的链表翻转方法
1. 处理第m-1个和第n+1个节点
1. 返回dummy->next
### C++
~~~
/**
* 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: The head of linked list.
* @param m: The start position need to reverse.
* @param n: The end position need to reverse.
* @return: The new head of partial reversed linked list.
*/
ListNode *reverseBetween(ListNode *head, int m, int n) {
if (head == NULL || m > n) {
return NULL;
}
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *node = dummy;
for (int i = 1; i != m; ++i) {
if (node == NULL) {
return NULL;
} else {
node = node->next;
}
}
ListNode *premNode = node;
ListNode *mNode = node->next;
ListNode *nNode = mNode, *postnNode = nNode->next;
for (int i = m; i != n; ++i) {
if (postnNode == NULL) {
return NULL;
}
ListNode *temp = postnNode->next;
postnNode->next = nNode;
nNode = postnNode;
postnNode = temp;
}
premNode->next = nNode;
mNode->next = postnNode;
return dummy->next;
}
};
~~~
### Java
~~~
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param ListNode head is the head of the linked list
* @oaram m and n
* @return: The head of the reversed ListNode
*/
public ListNode reverseBetween(ListNode head, int m , int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
// find the mth node
ListNode premNode = dummy;
for (int i = 1; i < m; i++) {
premNode = premNode.next;
}
// reverse node between m and n
ListNode prev = null, curr = premNode.next;
while (curr != null && (m <= n)) {
ListNode nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
m++;
}
// join head and tail before m and after n
premNode.next.next = curr;
premNode.next = prev;
return dummy.next;
}
}
~~~
### 源码分析
1. 处理异常
1. 使用dummy辅助节点
1. 找到premNode——m节点之前的一个节点
1. 以nNode和postnNode进行遍历翻转，注意考虑在遍历到n之前postnNode可能为空
1. 连接premNode和nNode，`premNode->next = nNode;`
1. 连接mNode和postnNode，`mNode->next = postnNode;`
**务必注意node 和node->next的区别！！**，node指代节点，而`node->next`指代节点的下一连接。
';