這題的倒讚數超多, 在寫的當下我也沒有辦法馬上get到, 我一直卡在怎麼一次做到位, 但後來看完討論區後看到其實在針對group even的人我們可以先切斷在做
/**
* 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* reverseList(ListNode *head){
if(!head) return head;
ListNode* prev = nullptr;
while(head){
ListNode *tmp = head->next;
head->next = prev;
prev = head;
head = tmp;
}
return prev;
}
ListNode* reverseEvenLengthGroups(ListNode* head) {
ListNode *dummy = new ListNode();
dummy->next = head;
ListNode* prev = dummy;
for(int len = 1; len< 1e5 && head;len++){
ListNode *tail = head;
ListNode *nextHead;
int j = 1;
while(j < len && tail && tail->next){
tail = tail->next;
j++;
}
nextHead = tail->next;
if(j % 2 == 0){
// even
tail->next = nullptr;
prev->next = reverseList(head);
prev = head;
head->next = nextHead;
head =nextHead;
}else{
// odd
prev = tail;
head = nextHead;
}
}
return dummy->next;
}
};首先一樣我們就先建立一個大家最熟悉的反轉陣列, 然後用一個prev 紀錄連接上一個head的node, 一開始的頭沒有怎麼辦, 我們先create一個dummy的node接著接上去
接著我們用一個for迴圈來記錄group的數量，從1到n, 一旦group 是偶數我們就要做一件事
我們已group 2當作一個例子
5 ---| -- > 2 -> 6 - -| --> 3
prev. head.tail. nextNode我們找到prev, head, tail, nextNode後, 就可以對中間的group2(2跟6)進行反轉, 先切斷tail 跟3的連結, 然後對head進行反轉, 最後再接回來
所以反轉回來後會變成這樣
5 ---| --> 6 ---> 2. |--> 3
prev. ReverseListReturn head nextNode首先我們先將prev接上return 回來的node, 接著我們可以看到原本的head已經來到尾端了, 我們把它接上nextNode, 然後再把prev, head, 更新到新一輪的位置, 這樣一個run就結束了, 之後的順序就以此類推
時間複雜度為O(n)
