Inversion de l'intervalle spécifié dans la liste des liens

Questions

Nombre de noeuds size Liste des liens m Position n Inversion de section entre les positions,Complexité temporelle requise O(n),Complexité spatiale O(1).

Idées

1. Déplacer à la position spécifiée avec un double pointeur： pre Passer à la position précédente de la position de départ de la Section de déplacement,cur Déplacer vers la position de départ de la Section de déplacement.
2. Connexion cur Avec cur L'élément suivant de,Déconnecter cur Avec next Connexion à;next Connectez - vous à pre Avant ce dernier élément;pre Pointage next.

Mise en œuvre du Code

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

class Solution {
    
public:
    /** * * @param head ListNodeCatégorie * @param m intTaille * @param n intTaille * @return ListNodeCatégorie */
    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, Donc l'indice de cette liste de questions vient de  1 C'est parti.,pre  Pointe vers la position avant le début de l'intervalle de retournement 
        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;
            // Déconnecter cur Avec next Connexion à
            cur->next = next->next;
            // À suivre next Déplacer vers pre  Avant l'élément suivant 
            next->next = pre->next;
            // Connexion pre Et next
            pre->next = next;
        }
        
        return dummyHead->next;
    }
};