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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <tuple>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    tuple<ListNode*,ListNode*,ListNode*> ReverseListWithEndNode(ListNode* head, int d) {
        // write code here
        auto *prev = new ListNode(head->val);
        auto *last = prev;

        int i = 0;
        ListNode *node = head->next;
        while(node!=nullptr && i<d){
                auto next = new ListNode(node->val);
                next->next = prev;
                prev = next;
                node = node->next;
                i++;
        }
        // 返回三个值 反转链表prev, 原表最后一个节点node，原表第一个节点last
        return make_tuple(prev, node, last);
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        int i=0;
        ListNode *root, *temp, *node=head;
        if(m>1){
            root = new ListNode(head->val);
            node = head->next;
            temp = root;
            i++;

        }
        
        for(;node!=nullptr;node=node->next,i++){
            if(i>=m-1 && i<=n-1){
                auto out = ReverseListWithEndNode(node, n-m);
                auto *prev = get<0>(out);
                auto *next = get<1>(out);
                auto *last = get<2>(out);
                if(m==1){
                    root = prev;
                    temp = last;
                    node = next;
                }
                else{
                    temp->next = prev;
                    temp = last;
                }
                
                last->next = next;
                node = last;
                i = n;
                if(node==nullptr) break;
            }else{
                auto *next = new ListNode(node->val);
                temp->next = next;
                temp = next;
            }
        }
        return root;
    }
};