Share my C++ AC code with ONE singlyLinkedList

  • 3
    class MinStack {
        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;
                    if (q->val < head->val)
                        head->val = q->val;
                    q = q->next;
        int top() {
            if (head->next)
                return head->next->val;
            return NULL;
        int getMin() {
            if (head->next)
                return head->val;
            return NULL;
        ListNode *head;

  • 1

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

  • 0

    Yeah, thank u! :D

  • 0

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

  • 0

    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.