博文中会简要介绍Leetcode P0092题目分析及解题思路。
“Reverse Linked List II”是一道比较基础的翻转链表的题目，它的原型题是p0206。思路也比较直接，首先找到第m个结点，然后再开始翻转。
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
具体思路在代码中已经注释了。最简单的思路就是先定位第m个结点和它的前缀结点，然后翻转链表直到第n个结点，最后再将m到n这一段的链表整体翻转即可。
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || m == n)
return head;
ListNode dummy = new ListNode(0, head);
ListNode curr = dummy, prev = dummy;
int count = m;
// Find the mth node and its previous node
// curr is mth node
while (count > 0) {
prev = curr;
curr = curr.next;
--count;
}
ListNode start = prev;
count = n-m;
// Reverse
while (count > 0) {
ListNode post = curr.next;
curr.next = prev;
prev = curr;
curr = post;
--count;
}
// prev is (n-1)th node, curr is nth node
start.next.next = curr.next;
curr.next = prev;
start.next = curr;
return dummy.next;
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (m == n)
return head;
ListNode *dummy = new ListNode(0, head);
ListNode *prev = dummy, *curr = dummy;
int count = m;
while (count > 0) {
prev = curr;
curr = curr->next;
--count;
}
count = n-m;
ListNode *start = prev;
while (count >= 0) {
ListNode *post = curr->next;
curr->next = prev;
prev = curr;
curr = post;
--count;
}
start->next->next = curr;
start->next = prev;
return dummy->next;
}
};