描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 𝑂(𝑛)O(n)，空间复杂度 𝑂(1)O(1)。
例如：
给出的链表为 1→2→3→4→5→𝑁𝑈𝐿𝐿  ,m=2,n=4,
返回 1→4→3→2→5→𝑁𝑈𝐿𝐿.

数据范围： 链表长度 0<𝑠𝑖𝑧𝑒≤10000，0<𝑚≤𝑛≤𝑠𝑖𝑧𝑒，链表中每个节点的值满足 ∣𝑣𝑎𝑙∣≤1000

要求：时间复杂度 𝑂(𝑛)O(n) ，空间复杂度 𝑂(𝑛)O(n)

进阶：时间复杂度 𝑂(𝑛)O(n)，空间复杂度 𝑂(1)O(1)

示例1

输入：

{1,2,3,4,5},2,4

返回值：

{1,4,3,2,5}

示例2

输入：

{5},1,1

返回值：

{5}

思路：

这道题的关键是：

①找到“需要转换的序列”前面“最后一个无需转换的节点位置”；

②找到“需要转换的序列”的“第一个节点”；

③找到“需要转换的序列”后“第一个无需转换的节点”。

代码

/**
 * 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 *cur = head, *tmp, *first = head;
        ListNode* nhead=new ListNode(-1);//哑节点（虚拟头节点），为了防止m=n=1时，tmp取不到最后一位不需要逆序的节点，而取到了和cur一样的第一位需要逆序的节点
        nhead ->next = head;
        tmp = nhead;
        
        for(int i = 1; i<m; i++)
        {
            tmp = cur;//tmp取到需要逆序的前一位
            cur = cur->next;//cur取到需要逆序的第一位
        } 
        first = cur;//first用于记住第一位需要逆序的节点，即逆序后的最后一位，用于在最后连接上剩下无需逆序的序列。
        for(int i = m; i <=n; i++)//循环需要逆序的序列中的节点，并连接在tmp后（记住：tmp正是无需逆序的最后一个节点）
        {
            ListNode *next = cur->next;//用于存放剩下的全部节点
            cur->next = tmp->next;
            tmp->next = cur;
            //以上两句是重点，由于无法直接在tmp节点后加节点cur，因此先把cur也连接在tmp的后一个节点，然后将tmp->next指向cur，则成功加入节点cur
            cur = next;
        }
        first->next = cur;//连接上剩下无需逆序的节点
        cur = nhead->next;//丢弃哑节点
        delete nhead;
        return cur;
    }
};