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

/**
 * 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) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *begin = head;
        ListNode *end = head;
        ListNode *bef = dummy;
        while (--m) {
            bef = begin;
            begin = begin->next;
        }
        ++n;
        while (--n) {
            end = end->next;
        }
        ListNode *tmp = bef;
        while (begin != end) {
            ListNode *nxt = begin->next;
            begin->next = tmp;
            tmp = begin;
            begin = nxt;
        }
        bef->next->next = end;
        bef->next = tmp;
        return dummy->next;
    }
};

思路：反转链表。

先定位几个位置：

* begin：下标m表示的链表节点。

* end：下标n + 1表示的链表节点。因为反转链表后需要把反转后的尾节点连接到原链表的后续节点上。

* dummy：虚拟头节点。因为头节点也可能被反转，反转后需要找到新的头节点。

* bef：下标m - 1表示的链表节点。因为反转链表后需要把反转后的头节点连接到原链表前面的节点上。

然后利用begin、end和bef，按照反转链表那样做即可。