1265. print-immutable-linked-list-in-reverse

문제: leetcode.com/problems/print-immutable-linked-list-in-reverse/

Account Login - LeetCode

 

1. Recursion

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        if(!head){
            return;
        }
        printLinkedListInReverse(head->getNext());
        head->printValue();
    }
};

 

Time complexity: O(N)

Space complexity: O(N)

 

2. Constant space complexity

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        ImmutableListNode* tail = NULL;
        
        while(head != tail){
            ImmutableListNode* node = head;
            
            while(node->getNext() != tail){
                node = node->getNext();
            }
            node->printValue();
            tail = node;
        }
    }
};

Time complexity: O(N^2)

Space complexity: O(1)

 

3. Linear time complexity and less than linear space complexity

class Solution {
public:
    void printDummy(ImmutableListNode* start, ImmutableListNode* end){
        vector<ImmutableListNode*> nodes; // space: sqrt(N)
        while(start != end){
            nodes.push_back(start);
            start = start->getNext();
        }
        
        for(int i = nodes.size() - 1; i >= 0; i--){
            nodes[i]->printValue();
        }
    }
    
    void printLinkedListInReverse(ImmutableListNode* head) {
        int total = 0;
        ImmutableListNode* node = head;
        while(node){
            total++;
            node = node->getNext();
        }
        
        int chunk = sqrt(total);
        vector<ImmutableListNode*> nodes; // space: sqrt(N)
        node = head;
        
        int count = 0;
        
        while(node){
            if(count % chunk == 0){
                nodes.push_back(node);
                count = 0;
            }
            node = node->getNext();
            count++;
        }
        nodes.push_back(NULL);
        
        for(int i = nodes.size() - 2; i >= 0; i--){ // time: sqrt(N)
            printDummy(nodes[i], nodes[i + 1]); // space: sqrt(N) * sqrt(N) == N
        }
    }
};

Time complexity: O(N)

Space complexity: O(sqrt(N)) -> sqrt(N)이 아니라 다 합치면 N이 되야할거같은데?