1

I am practicing the Leetcode question "Next Greater Node in Linked List" and here is my code:

#define STACK_SIZE (10000U)

typedef struct ListNode Node;

static int stack[STACK_SIZE];
static int top=-1;

bool isEmpty()
{
    return (top==-1);
}

void addToStack(int element)
{
    stack[++top]=element;
}

void remFromStack()
{
    --top;    
}

int getStackTop()
{
    return stack[top];
}

 typedef struct ListNode Node;

 int* nextLargerNodes(struct ListNode* head, int* returnSize) {

        if (head == NULL) {

            *returnSize = 0;
            return NULL;
        }

        int len = 0;
        Node *temp = head;

        while (temp) {
            len++;
            temp = temp->next;
        }

        if (len > 0) {
            int *result = malloc(len * sizeof(int));
            *returnSize = len;

            if (result == NULL) {
                return NULL;
            }

            int j = 0;
            while (j < len) {
                result[j++] = 0;
            }

            temp = head;
            addToStack(temp->val);
            j = 0;
            while (temp->next) {
                temp = temp->next;
                j++;

                if (getStackTop() > temp->val) {
                    addToStack(temp->val);
                } else {
                    int i = 0;
                    while (!isEmpty()) {
                        i++;
                        result[j - i] = temp->val;
                        remFromStack();
                    }
                    addToStack(temp->val);
                }
            }
            return result;
        } else {
            return NULL;
        }

}

And I am getting the following error:

=================================================================
==29==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6030000
WRITE of size 4 at 0x60300000000c thread T0
 #2 0x7f55143382e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.s
0x60300000000c is located 4 bytes to the left of 20-byte region [0x60300
allocated by thread T0 here:
 #0 0x7f55157c22b0 in malloc (/usr/local/lib64/libasan.so.5+0xe82b0)
 #3 0x7f55143382e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.s

I am not sure what's wrong here.

Tried making sure all the code is correct, and when I test the code against my own test cases, it works perfectly fine, but when I submit the code, only then I am getting this error.

Note: The returned array must be malloced, assume caller calls free().

The utility functions dont have any malloc/ calloc called in them, so, that removes them from the equation.

12
  • You didn't provide all the code, but it sounds like result[j - i] = temp->val; is accessing memory you didn't allocate, probably because i is greater than j (so you are accessing result[-1]) Commented May 12, 2019 at 1:15
  • Check your isEmpty() and remFromStack() functions. Commented May 12, 2019 at 1:16
  • but the AddressSanitizer is pointing towards malloc. Commented May 12, 2019 at 1:17
  • @mnistic . I have added all the code now. Commented May 12, 2019 at 1:21
  • Unrelated: Get rid of if (len > 0) when execution gets there len is always > 0. Commented May 12, 2019 at 1:28

1 Answer 1

1

Sizeof behaves differently on Leetcode.

Try to use strlen (if you are using char) OR other methods to find the size of a datatype you are trying to use.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.