春季每日一题(3.18)反转链表Ⅱ

反转链表Ⅱ

原题戳这里

题解

/**
 * 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) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto a = dummy;			//虚拟头结点，女少口阿！！！！
       	//先找到最后一个不要换的结点
        for (int i = 0 ; i < left - 1 ; i ++ ) a = a->next;

		//b和c一起操作，循环里面有一个d用来暂时存储c的next，最后记得整体移动
		//整体移动的次数根据边数来判断
		//分析最后for循环结束后的情况
        auto b = a->next, c = b->next;
        for(int i = 0 ; i < right - left ; i ++ ){
            auto d = c->next;
            c->next = b;
            b = c, c = d;
        }
        a->next->next = c;
        a->next = b;
        return dummy->next;
    }
};
           

• 虚拟头结点很妙啊！！！for循环操作和上一题其实一样