力扣 92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

将中间反转，再拼接

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* mid=new ListNode (0);
        ListNode* left=new ListNode (0);
        ListNode* right=new ListNode (0);
        ListNode* hmid=mid;
        ListNode* hleft=left;
        ListNode* hright=right;
        int l=1;
        ListNode* p=head;
        while(p){
            if(l>=m&&l<=n){
                ListNode* w=new ListNode (p->val);
                hmid->next=w;
                hmid=w;
            }
            else if(l<m){
               ListNode* w=new ListNode(p->val);
               hleft->next=w;
               hleft=w;
            }
            else if(l>n){
                 ListNode* w=new ListNode(p->val);
                  hright->next=w;
                  hright=w;
            }
            l++;
            p=p->next;
        }
        ListNode* re=reserve(mid->next);
        ListNode* pmid=re;
       while(pmid->next){
           pmid=pmid->next;
       }
       pmid->next=right->next;
       ListNode* pleft=left;
       while(pleft->next){
           pleft=pleft->next;
       }
       pleft->next=re;
      return left->next;
    }
    ListNode* reserve(ListNode* head){
        if(!head){
            return head;
        }
        ListNode* pre=head;
        ListNode* cur=NULL;
        while(pre){
            ListNode* temp=pre->next;
            pre->next=cur;
            cur=pre;
            pre=temp;
        }
        return cur;
    }
};