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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
   void reverse(ListNode* head,ListNode* end) {
        if (head == nullptr || head->next == nullptr || head == end)
            return ;
        reverse(head->next,end);
        head->next->next = head;
        head->next = nullptr;
        // return new_head;
    }


    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int i=1;
        ListNode* tmp = head;
        ListNode* start = nullptr;
        ListNode* end = nullptr;
        ListNode* pre = nullptr;
        ListNode *after = nullptr;
        while(tmp != nullptr){
            if(m != 1 && i == m-1)
                pre = tmp;
            if(i == m){
                start = tmp;
            }
            if(i == n){
                end = tmp;
            }

            i++;
            tmp = tmp->next;
        }
        if(end->next != nullptr)
            after = end->next;
        reverse(start,end);
        // cout << start->val <<end;
        if(m != 1){
            pre->next = end;
            start->next = after;
            return head;
        }
        else{
            start->next = after;
            return end;
        }
    }
};