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

/**
 * 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) {
        if(m == n) return head; // 如果 m == n，说明没有发生反转，直接返回头节点
        ListNode* result = head;    // 用来找第n+1个节点
        ListNode* find_before_head = head;  // 用来找第m-1个节点
        ListNode* before_m = new ListNode(-1); // 用来记录第m-1个节点
        ListNode* after_n = NULL;   // 用来记录第n+1个节点
        // 找第m - 1个节点
        if(m == 1){
            before_m->next = head;
        }else{
            while(find_before_head){    // m > 1时，就这么找第m-1个节点
                m--;
                if(m == 1) before_m = find_before_head;
                find_before_head = find_before_head->next;
            }
        }
        // 找第n+1个节点
        while(result){
            n--;
            if(n == -1){
                after_n = result;
            }
            result = result->next;
        }
        ListNode* pre = after_n;    // 参考反转链表，pre此时应是第n+1个节点
        ListNode* cur = before_m->next; // cur此时应是第m个节点
        while(cur != after_n){
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        before_m->next = pre;
        if(before_m->val == -1) return before_m->next;
        return head;
    }
};