2074. Reverse Nodes in Even Length Groups

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int k =0;
    
    ListNode* reverseN(ListNode *l,ListNode *r){
        ListNode *pre = new ListNode(-1), *cur =l;
        pre->next = l;
        while(cur->next !=r){
            ListNode *temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return pre->next;
    }
    int getSize(ListNode *head){
        int size=0;
        for(;head;head=head->next) size++;
        return size;
    }
    ListNode* reverseEvenLengthGroups(ListNode *head, int size){
        
        if(!head) return nullptr;
        ListNode *a = head, *b =head;
        k++;
        int n = min(size,k);
        size -=k;
        int c = 0;
        while(n--){
            if(b==nullptr) return head;
            b=b->next;
            c++;
        }
        if(c%2==0){
            ListNode* newhead = reverseN(a,b);
            a->next = reverseEvenLengthGroups(b, size);
            return newhead;
        }
        else{
            ListNode *p =a;
            while(p->next !=b) p=p->next;
            p->next = reverseEvenLengthGroups(b, size);
            return a;
        }
    
    }
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        int size = getSize(head);
        return reverseEvenLengthGroups(head, size);
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)