[notes for question brushing] specified interval reversal in the linked list

subject ：

describe

Set the number of a node to size Linked list m  Position to  n Interval reversal between positions , Time complexity required  O(n)O(n), Spatial complexity  O(1)O(1).
for example ：
The list given is  1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
return  1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.
 

Data range ：  Chain length  0 < size \le 10000<size≤1000,0 < m \le n \le size0<m≤n≤size, The value of each node in the linked list meets  |val| \le 1000∣val∣≤1000

requirement ： Time complexity  O(n)O(n) , Spatial complexity  O(n)O(n)

Advanced ： Time complexity  O(n)O(n), Spatial complexity  O(1)O(1)

Example 1

Input ：

{1,2,3,4,5},2,4

Return value ：

{1,4,3,2,5}

Example 2

Input ：

{5},1,1

Return value ：

{5}

Topic link ： Reverse the specified interval in the linked list _ Niuke Tiba _ Cattle from (nowcoder.com)

answer ：

        As long as you master the reverse linked list, you can generally solve this problem , As for the given interval, you only need to traverse here .

        Our goal is to reverse the entire list while traversing . So can we fix the initial node , Then every time you cycle , Just move the next fixed node to the front of the fixed node , Let the fixed node in front of the fixed node point to this mobile node , Then the mobile node points to the next fixed node at the beginning .（ Point to the first node at the beginning , Then point to the second , This is equivalent to rearranging the front fixed node and the fixed node in reverse order ）. In this way, you can move by how many steps .

        The front fixed node is res, Fixed node is cur. In order to prevent the first row from the beginning , Then the front fixed node needs to create a head node , It's worth it , Then point to the head , In this way, when returning, you can return the head it points to .

        Then through the cycle, that is i < m Find the first node ,res It is equal to the previous node , that cur Is to point to the latter .

Code ：

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    // write code here
    struct ListNode* res = (struct ListNode*)malloc(sizeof(struct ListNode));
    res->next = head;
    struct ListNode* pre = res;
    struct ListNode* cur = head;
    for (int i = 1; i < m; i++)
    {
        pre = cur;
        cur = cur->next;
    }
    
    for(int i = m; i < n; i++)
    {
        struct ListNode* temp = cur->next;
        cur->next = temp->next;
        temp->next = pre->next;
        pre->next = temp;
    }
    return res->next;
}