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

这道题的思路其实简单，看到了空间复杂度可以是O(N)，瞬间就想到了用一个指针数组来存每一个node的地址，然后用一个int数组存变换前和变换后数组index的对应关系(原序号0，1，2，3，4，变换后序号可能就是0，3，2，1，4)，然后将其全部串在一起就行了

 * 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
        if(m == n)
            return head;
        if(n-m==0)
            return head;
        if(head == NULL||head->next == NULL)
            return head;
        ListNode* node = new ListNode(-1);
        ListNode* cur = node;
        ListNode* once = head;
        ListNode *a[1100];
        int b[1100] = {0};
        int i = 0 ;
        
        while(once)
        {
            a[i] = once;
            once = once->next;
            if(m-1<=i&&i<=n-1)
            {
                //cout<<"i = "<<i<<endl;
                b[i] = m+n-i-2;
                //cout<<"b[i] = "<<b[i]<<endl;
            }
            else
                b[i] = i;
            i++;
        }
        int j = 0 ;
        while(j<i)
        {
            cur->next = a[b[j]];
            cur = cur->next;
            j++;
        }
        cur->next = NULL;
        return node->next;
        
       
    }
};