题解 | #链表内指定区间反转#

思路如下：

1.首先考虑简单点的场景，反转整个链表

如果是反转整个链表的话，我们要做的是将原本某个节点的next指向这个节点的前一个节点（将前一个节点记为pre）

对与 [1 -> 2 -> 3 -> 3 -> 4 -> null] 这个链表来说：

1的pre为null（1节点没有前节点）

2的pre为1

3的pre为2

4的pre为3

因此，对于每个节点我们必须要知道它的pre。我们在遍历链表的时候就不断将当前的节点更新给pre，那么对与当前节点的next来说，pre就是已知的了。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = NULL;
        while(pHead){
            ListNode *temp = pHead->next;
            pHead->next = pre;
            pre = pHead;
            pHead = temp;
        }
        return pre;
    }
};

2.弄清了反转整个链表，现在我们再来考虑考虑链表内指定区间反转（区间m到n）该怎么操作

通过反转整个链表，我们可以知道pre是反转的关键，因此首先找到pre

我们首先根据m和n找到bg和ed，bg为第m个节点的前一个节点，ed为第n个节点，如下所示：

对于m = 2, n = 5，链表： [1 -> 2 -> 3 -> 3 -> 4 -> 5 -> 6-> null] ，那么此时的bg为1，ed为5，

区间[m, n]，即[2, 5]为：[2 -> 3 -> 3 -> 4 -> 5]

此时

3的pre为2

4的pre为3

5的pre为4

那么2的pre是哪个，是null吗，是1吗，答案都不是。2的pre是为ed（上述样例里的ed为5）的后一个节点，因为在反转后当前节点pre是赋给了当前节点的next，就是说最终pre节点会成为当前节点的next节点，对于m = 2, n = 5，链表： [1 -> 2 -> 3 -> 3 -> 4 -> 5 -> 6-> null] 反转之后，2的next是6，因此在反转前2的pre为6。

找到所有的pre之后，对于区间[m, n]只需要和反转整个链表的操作一样即可，但这里有两个细节：

第一，因为bg为第m个节点的前一个节点，故区间的开始是m，即bg的next，但是bg可能为null，这种情况就是m=1，那么区间的开始就是链表的表头节点

第二，若bg不是null，那么需要还需要更新一下bg的next，因为区间被反转了，那么bg的next就是ed了，例如上面的例子：对于m = 2, n = 5，链表： [1 -> 2 -> 3 -> 3 -> 4 -> 5 -> 6-> null] 反转之后：[1 -> 5 -> 4 -> 3 -> 2 -> 1 -> 6-> null]，还需修改一下1（1就是bg）的next为5（5就是ed）

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode *root = head;
        ListNode *bg = nullptr, *ed = nullptr;
        while(m > 0 || n > 0){
            --m, --n;
            if(m > 0){
                bg = head;
            }
            ed = head;
            head = head->next;
        }
        // 此时的head就是ed的后一个节点
//         cout<<bg->val<<endl;
//         cout<<ed->val<<endl;
        ListNode *pre = head, *cur = nullptr;
        if(bg){
            cur = bg->next;
            bg->next = ed;
        } else{
            cur = root;
        }
        while(cur != head){
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return bg ? root : ed;
    }
};