[specified interval inversion in BM2 linked list]

Reverse the specified interval in the linked list

Title source

Cattle from ： Reverse the specified interval in the linked list

Title Description

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→2→3→4→5→NULL,m=2,n=4,
return 1→4→3→2→5→NULL.

Data range ： Chain length 0 <size≤1000,0 < m≤n≤size, The value of each node in the linked list meets ∣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

Output

{5}

Thought analysis

• Define a virtual head node , Prevent the head node of the linked list from being inverted
• Find the starting position of the interval to be reversed and its precursor node
• Reverse from the starting position with the method of reverse of single linked list
• Splice the inverted part with the original linked list
• Returns the next node of the virtual head node

Code display

ListNode* reverseBetween(ListNode* head, int m, int n) {
    
    if (head == NULL)
    {
    
        return NULL;
    }
    // The head node may also be reversed , Define a virtual head node 
    ListNode* myhead = new ListNode(0);// Apply for a new node 
    myhead->next = head;// The new node is connected with the original head node 
    ListNode* cur = myhead;

    for (int i = 0; i < m - 1; i++)
    {
    
        cur = cur->next;
    }
    ListNode* prev = cur;// Start reversing the previous node of the point 
    ListNode* start = prev->next;// The node that begins to reverse 

    cur = start->next;
    ListNode* before = start;
    ListNode* next = nullptr;
    while (m < n)
    {
    
        next = cur->next;
        cur->next = before;
        before = cur;
        cur = next;
        m++;
    }
    prev->next = before;//prev Of next Point to the starting point after inversion 
    start->next = cur;//start Become after reversing end, therefore start Of next Point to the next node at the end of the original 
    return myhead->next;
}
};