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

解题思路： 寻找需要翻转的链表的起始点s和终止点e, 记录s的前一个节点pre_s 和e的后一个节点after_e; 对s到e进行翻转，得到翻转后的新起始点 new_s 和 new_e； pre_s ->next = new_s; new_e ->next = after_e;

/**
 * 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类
     */

    /*
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head ;
        ListNode* pre = dummyhead ;
        ListNode* cur = head ;
        for(int i = 1; i< m; i++){
            pre = cur;
            cur = cur->next;
        }
        for(int i = m; i<n; i++){
            ListNode* temp = cur->next;

            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return dummyhead->next;
    }*/
    //  翻转start , end 区间的链表
    pair<ListNode*, ListNode*> reListNode(ListNode* start, ListNode* end ) {
        ListNode* cur = start;
        int length = 1;
        while (cur != end) {
            length++;
            cur = cur->next;
        }
        ListNode* pre = start;
        cur = start->next;
        while (pre != end) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        ListNode* reversedStart = end;
        ListNode* reversedEnd = end;
        while (length-- && length > 0) {
            reversedEnd = reversedEnd->next;
        }
        return make_pair(reversedStart, reversedEnd);
    }
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* cur = head;
        ListNode* pre = dummyhead;

        while (--m) {
            cur = cur->next;
            pre = pre->next; // 翻转起始点的前一个节点
        }
        ListNode* start = cur; 
        cur = head;

        while (--n) {
            cur = cur->next;
        }
        ListNode* node = cur->next; // 翻转终止点的后一个节点
        ListNode* end = cur; 

        auto result = reListNode(start, end);
        pre->next = result.first;
        // cout << result.first->val << endl; //测试结果
        result.second->next = node;
        // cout << result.second->val << endl; //测试结果
        //ListNode* c = head;
        //while (c != nullptr) {
        //    cout << c->val;
        //    c = c->next;
        //} 

        return dummyhead->next;
    }
};