Share my C++ AC code with ONE singlyLinkedList


  • 3
    L
    class MinStack {
    
    public:
        struct ListNode {
            int val;
            ListNode *next;
            ListNode(int x) : val(x), next(NULL) {}
        };
    
        MinStack() {
            // We use the first element store the minimum value.
            head = new ListNode(INT_MAX);
        }
    
        void push(int x) {
            ListNode *newData = new ListNode(x);
            newData->next = head->next;
            head->next = newData;
    
            // If the pushed element is smaller than the current minimum, then change the minimum value.
            if (x < head->val)
                head->val = x;
        }
    
        void pop() {
            if (!head->next)
                return ;
    
            ListNode *p = head->next;
            head->next = head->next->next;
    
            // If the popped element is the same as the current minimum, then find the new minimum value.
            if (p->val == head->val){
                head->val = INT_MAX;
                ListNode *q = head->next;
                while(q){
                    if (q->val < head->val)
                        head->val = q->val;
                    q = q->next;
                }
            }
            delete(p);
        }
    
        int top() {
            if (head->next)
                return head->next->val;
            return NULL;
        }
    
        int getMin() {
            if (head->next)
                return head->val;
            return NULL;
        }
    
    private:
        ListNode *head;
    };

  • 1
    X

    Man, you should use new and delete together, not new and free.


  • 0
    L

    Yeah, thank u! :D


  • 0
    P

    Your pop() function is taking linear time!!!!
    It was clearly mentioned in the question to provide constant time


  • 0
    L

    Yes, in the worst case, pop() function is taking linear time. But in most of test cases, pop() function maybe just takes O(1) time, and this solution just need O(n+1) space, So it AC.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.