春季每日一題(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循環操作和上一題其實一樣