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

流程:

1. 在给定的链表前面加一个虚拟头, 方便写程序.
2. 从第1个结点开始往后走, 直到到达第m个结点, 记录下第m个结点之前的结点before.
3. 把第m~n个结点插到依次另一个虚拟头的后面, 实现反转. 完成后指针指向第n+1个结点.
4. 把第0~before个结点, 第n+1~end个结点, 还有反转的部分连接起来即可.

class Solution {
  public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode _emptyhead{0};
        ListNode* emptyhead{&_emptyhead};
        ListNode _tmp_emptyhead{0};
        ListNode* tmp_emptyhead{&_tmp_emptyhead};
        ListNode* before{emptyhead};
        ListNode* node{head};
        int m_i {1}, n_i{m};

        // Add a virtual head node.
        emptyhead->next = head;
        while (m_i++ < m && node != nullptr) {
            before = node;
            node = node->next;
        }

        while (n_i++ <= n && node != nullptr) {
            ListNode* nodenext = node->next;
            node->next = tmp_emptyhead->next;
            tmp_emptyhead->next = node;
            node = nodenext;
        }

        before->next->next = node;
        before->next = tmp_emptyhead->next;
        
        return emptyhead->next;

    }
};