leetcode92. 反转链表 II

分析

用cur找到left所在的位置，pre指向cur之前的位置，last指向cur后一个位置，利用头插法，将left到right的节点插到pre中。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy=new ListNode();
        dummy->next=head;
        ListNode* cur=head;
        int index=1;
        ListNode* pre=dummy;//防止从1开始旋转
        while(index<left){
            pre=cur;
            cur=cur->next;
            index++;
        }
        ListNode*last;
        while(index<right){
            last=cur->next;
            cur->next=last->next;
            last->next=pre->next;
            pre->next=last;
            index++;
        }
        return dummy->next;
    }
};