方法一：栈
解题思路：
  • 判断参数head是否为空，若空则直接返回；判断m是否等于n，相等则无需进行操作，直接返回；
  • 由于题目给出的链表是不带头结点的，所以令i=1，work=head，首先用work指针，从链表头部开始进行遍历，遍历前m-1元素，最后一次遍历时，work指向第m个元素，同时以start指针记录work的当前位置以便下一次遍历时能够直接从第m个元素开始；
  • 顺序遍历第m到第n位置的元素，并用栈进行存储；
  • 再次从start出开始进行顺序遍历直到栈空，每遍历一个新结点时将栈顶元素赋值给当前结点，实现反转链表。

    时间复杂度：O(n)
    空间复杂度: O(1) 
  • ListNode* reverseBetween(ListNode* head, int m, int n) 
{
        if(!head || m == n)
            return head;
        ListNode *work = head;
        stack<int> stk;
        int i = 1;
        while(i <= m-1) {           // 找到第m个结点
            work = work->next;
            ++i;
        }
        ListNode *start = work;    // 记录第m个结点的指针
        while(i <= n) {            // 记录第m到第n个结点的值
            stk.push(work->val);
            work = work->next;
            ++i;
        }
        work = start;              // 从第m个结点开始遍历
        while(!stk.empty()) {      // 赋值实现反转
            work->val = stk.top();
            stk.pop();
            work = work->next;
        }
        return head;
}

    方法二： 三指针
    解题思路:
    • 判断参数head是否为空，若空则直接返回；判断m是否等于n，相等则无需进行操作，直接返回；
    • 创建一个头结点head_node，以便对整个链表的操作实现统一；
    • 指针begin初始化为头节点head_node，begin将作为待反转链表第一个结点的前驱指针。然后通过变量i(初始化为0)记录当前遍历的结点个数，顺序遍历链表的前m-1个结点时，begin不断向前移动，最终指向第m-1个结点；
    • 指针start指向待反转链表的第一个结点，初始化为begin->next;指针finish指向待反转链表的最后一个结点，初始化为begin。然后在顺序遍历到第n个结点的过程中，finish不断向前移动，直到指向第n个结点。
    • 指针end指向待反转链表的最后一个结点的下一个位置；
    • 采用三指针法反转链表：
      • 初始时，指针p指向start，指针q指向start->next；
      • 反转过程: tmp = q->next; q->next = p；p = q；q = tmp
      • 结束条件：q == finish
    • 最后一步：将反转后的链表与其余begin之前的链表和end之后的链表进行连接：
    begin->next = finish;    start->next = end;
    示意图：

     
    ListNode* reverseBetween(ListNode* head, int m, int n) 
{
        if(!head || m == n)
            return head;
        ListNode *head_node = new ListNode(-1);
        head_node->next = head;         // 创建链表的头结点
        
        ListNode *begin = head_node;    // begin指向待反转链表的前一个结点
        int i = 0;
        while( i <= m -2) {             // 循环结束, begin指向第m-1个结点
            begin = begin->next;
            ++i;
        }
        ListNode *start = begin->next;
        ListNode *finish = begin;
        while( i < n) {                // 循环结束, finish指向第n个结点
            finish = finish->next;
            ++i;
        }
        ListNode *end = finish->next;  // end指向第待反转链表的下一个结点
        
        ListNode *p = start;
        ListNode *q = start->next;
        begin->next = nullptr;
        finish->next = nullptr;
        
        while(p != finish) {
            ListNode *tmp = q->next;
            q->next = p;
            p = q;
            q = tmp;
        }
        
        begin->next = finish;
        start->next = end;
        
        head = head_node->next;
        delete head_node;
        return head;
}
    时间复杂度：O(n)
    空间复杂度: O(1)