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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
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
        // 如果头节点就是空，直接返回，如果 m 和 n 相等，不用反转，直接返回
        if (!head || m == n) return head;

        // 创建一个 dummy 节点，接到头节点前面，纯纯套路
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;

        // 先挪到要反转的前面一个位置上
        for (int i = 1; i < m; ++i) {
            prev = prev->next;
        }

        // start 用来往后走，then 用来局部反转
        ListNode* start = prev->next;
        ListNode* then = start->next;

        // 画个图
        // i = 0
        //  1->2->3->4->5->NULL, m = 2, n = 4
        //     ^  ^
        //     |  |
        // start  |
        //        then
        //
        // start->next = then->next;
        //      ---->
        //     |     |
        //  1->2xx3->4->5->NULL, m = 2, n = 4
        //
        // then->next = prev->next;
        //      ---->
        //     |     |
        //  1->2<-3xx4->5->NULL, m = 2, n = 4
        //
        // prev->next = then;
        //      ---->
        //     |     |
        //  1xx2<-3xx4->5->NULL, m = 2, n = 4
        //  |     |
        //   ---->
        //
        // then = start->next;
        //      ---->
        //     |     |
        //  1xx2<-3xx4->5->NULL, m = 2, n = 4
        //  |     |  ^
        //   ---->   |
        //           then
        // 整理一下
        //  1->3->2->4->5->NULL, m = 2, n = 4
        //        ^  ^
        //        |  |
        //    start  |
        //           then
        // 
        // 下一个循环同理，不画了
        

        for (int i = 0; i < n - m; ++i) {
            start->next = then->next;
            then->next = prev->next;
            prev->next = then;
            then = start->next;
        }

        return dummy.next;
    }
};