Specified interval inversion in the linked list

problem

Set the number of a node to size Linked list m Position to n Interval reversal between positions , Time complexity required O(n), Spatial complexity O(1).

Ideas

1. Use double pointer to move to the specified position ： pre Move to the previous position of the starting position of the mobile section ,cur Move to the starting position of the mobile section .
2. Connect cur And cur Next element of , To break off cur And next The connection of ;next Connect to pre Before the next element ;pre Point to next.

Code implementation

/** * struct ListNode { * int val; * struct ListNode *next; * }; */

class Solution {
    
public:
    /** * * @param head ListNode class  * @param m int integer  * @param n int integer  * @return ListNode class  */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
    
        // write code here
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* pre = dummyHead;
        // 0 < m < size, So the subscript of the linked list of this question is from  1  Start ,pre  Point to the position before the beginning of the overturning section 
        for (int i = 1; i < m; i++)
        {
    
            pre = pre->next;
        }
        ListNode* cur = pre->next;
        
        for (int i = m; i < n; i++)
        {
    
            ListNode* next = cur->next;
            //  To break off  cur  And  next  The connection of 
            cur->next = next->next;
            //  The following  next  Move to  pre  Before the next element 
            next->next = pre->next;
            //  Connect  pre  and  next
            pre->next = next;
        }
        
        return dummyHead->next;
    }
};