算法(模拟)

借鉴了y总的图解。

解题思路

1. 首先特判，如果(m = n)，就没有翻转，直接return head即可。
2. 因为可能会翻转头结点head，所以构建一个虚拟头结点dummy，来保护头结点。dummy->next = head。
3. a是第m个节点的前一个节点的位置，b是第m个节点的位置，c是第n个节点的下一个位置，d是第n个节点的位置。这里要注意，a和d的初始值是dummy，它们的next指向的是head，这样可以更好理解a和d具体位置的求解。
4. 接下来，对m和n之间的节点进行处理，让m + 1到n这条链上的节点的next指针反转，指向自己的前驱节点，因为a b c d四个位置是不能变的，所以新建立3个变量p q o，因为改变的是m + 1 ~ n个节点的next指针指向，所以让q作为第m + 1个节点，o来存储反转前的后继结点，p则对应q的前驱节点。可以理解为q是当前节点，o和p分别维护的是后继和前驱节点。当q指针指向位置c的时候，意味着第n个节点(d)的next指针已经指向了它的前驱，那么反转处理到这里就结束了。
5. 最后，将a的next指针指向d，也就是第m个节点的前驱节点指向第n个节点，第m个节点指向第n+1个节点，返回dummy->next，就得到了答案。

代码

/**
 * 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 m, int n) 
    {
        if(m == n) return head;

        ListNode *dummy = new ListNode(-1);
        dummy->next = head;

        ListNode *a = dummy;
        ListNode *d = dummy;
        for(int i = 0; i < m - 1; i ++) a = a->next;
        // for(int i = 0; i < n - 1; i ++) d = d->next;
        for(int i = 0; i < n; i ++) d = d->next;
        auto b = a->next;
        auto c = d->next;

        // for(auto p = b, q = p->next; p != c;)
        for(auto p = b, q = b->next; q != c;)
        {
            auto o = q->next;
            q->next = p, p = q, q = o;
        }

        a->next = d;
        b->next = c;

        return dummy->next;
    }
};