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

如果题目中提供了结点的构造函数，可以建立一个虚头结点，避免头节点处于区间翻转时的分类讨论。

本题中没有提供，所以要针对有没有头节点进行分类讨论

#include <iostream>
class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==1) return rever(head, n-m+1); //如果头结点在区间内
        ListNode *new_n = head;
        int cnt = 1;
        while (head) {
            cnt++;
            if(m == cnt) break;;
            head = head->next;
        }
        ListNode * cur = rever(head->next, n-m+1);
        head->next = cur;
        return new_n;
 
    }
    ListNode * rever(ListNode* head, int len){
    
        ListNode * p = nullptr;
        ListNode * tail = head;  //用来连接后续的链表
 
        while(head && len){
            //cout << head->val <<" " <<len <<endl;
            ListNode *temp = head;
            head = head->next;
            temp->next = p;
            p = temp;
            len--;
        }
        if(head) tail->next = head;
        return p;
    }
};