链表内的指定区间反转

思路首先建立一个哨兵位记dummy如果头节点也在范围内可以方便操作。1如果头节点为空或者m等于n就不用转了直接返回。搞一个pre来找到m前的节点方便我们插入。pre一开始为dummy因为如果m为1pre就是dummy那个位置 不为1我们可以移动。i初始为1因为m和n不是下标是第几个元素。cur为区间第一个节点即一开始pre的next在创建一个next来构成三节点。range为n-m1但因为cur为第一个节点所以循环n-m即可class Solution {public:ListNode* reverseBetween(ListNode* head, int m, int n) {if (!head || m n) return head; // 特殊情况处理ListNode* dummy new ListNode(0); // 虚拟头节点dummy-next head;ListNode* pre dummy;// 1. 找到第 m-1 个节点prefor (int i 1; i m; i) {pre pre-next;}// 2. 准备开始反转ListNode* cur pre-next; // 区间第一个节点ListNode* next;for (int i 0; i n - m; i) { // 移动 n-m 次next cur-next; // 下一个要移动的节点cur-next next-next; // 跳过 nextnext-next pre-next; // next 插入到 pre 后面pre-next next; // pre 指向新的头}ListNode* newHead dummy-next;delete dummy; // 释放虚拟节点return newHead;}};