【c++】【leetcode92】翻转链表Ⅱ（O（n））

反转链表Ⅱ

• 定义两个新结点，root指向原本链表的头，he指向从left位置开始的结点。
• 定义back，end，p指针，back指向left位置前一个结点，end指向right位置的结点，p指向right位置后一个结点。
• 中间位置进行反转链表，区域位置保持不变，如下如所示（back->next = he->next）
• end一开始指向left位置的结点，最后仍然指向该结点，只是这个结点被反转到最开始right的位置
  

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* he = new ListNode;//指向原本的链表
        ListNode* root = new ListNode;
        root->next = head;
        ListNode* back = root;
        for(int i = 1;i < left;++i){
            back = back->next;//back在left前一位
        }
        ListNode* end = back->next;//end指向left
        ListNode* p = end;//p指向最后剩下的
        ListNode* q = end;
        for(int i = left;i <= right;++i){
            q = p->next;
            p->next = he->next;
            he->next = p;
            p = q;
        }
        back->next = he->next;
        end->next = p;
        return root->next;
    }
};