I am working on the LeetCode problem 189. Rotate Array:
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
I wanted to solve it with a circular linked list.
This is my code:
#include <stdio.h>
#include <stdlib.h>
// Structure of a linked list node
struct node {
int info;
struct node* next;
};
// Pointer to last node in the list
struct node* last = NULL;
void rotate(int* nums, int numsSize, int k){
int i;
struct node* temp;
for (i = 0; i < numsSize; i++)
{
// Initialize a new node
temp = (struct node*)malloc(sizeof(struct node));
if (last == NULL) {
temp->info = nums[i];
temp->next = temp;
last = temp;
}
else {
temp->info = nums[i];
temp->next = last->next;
// last node now has reference
// of the new node temp
last->next = temp;
}
}
i=0;
temp = (struct node*)malloc(sizeof(struct node));
temp = last;
while (i < k)
{
temp = temp->next;
i++;
}
last = temp;
temp = last->next;
i=numsSize-1;
//rotate
do {
printf("Data = %d\n", temp->info);
nums[i]=temp->info;
temp = temp->next;
i--;
} while (temp != last->next);
}
The program runs well on my computer and produces the correct result for each possible test case, but when I submit the code on LeetCode, it gives the following Runtime error:
heap-buffer-overflow
=================================================================
==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000022c at pc 0x55ee87988926 bp 0x7ffd33a4b650 sp 0x7ffd33a4b640
WRITE of size 4 at 0x60200000022c thread T0
#2 0x7f79c721f0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x60200000022c is located 4 bytes to the left of 16-byte region [0x602000000230,0x602000000240)
allocated by thread T0 here:
#0 0x7f79c7e64bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
#3 0x7f79c721f0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff8000: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa 00 00
0x0c047fff8010: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa fd fa
0x0c047fff8020: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8030: fa fa fd fa fa fa 00 00 fa fa fd fa fa fa fd fa
=>0x0c047fff8040: fa fa fd fa fa[fa]00 00 fa fa 00 00 fa fa 00 00
0x0c047fff8050: fa fa 00 00 fa fa 00 00 fa fa fa fa fa fa fa fa
0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==31==ABORTING
What should I do to fix this error?
The problem is that you have defined last as a global variable, and so when multiple tests are run, that global variable will not always be NULL when the function starts to do its thing, yet that is what your logic expects.
So you should move that declaration inside the function, so that last is initialised at each run of the function.
With that your code will be accepted.
It is not good that you allocate memory, but don't free it. This means memory is leaking.
Also, this can be solved without additional linked list, even without O(n) auxiliary memory. You can cycle through the array with k steps and move values in-place. Repeat such cycles until all values have been moved.
Below a spoiler implementation of that idea:
void rotate(int* nums, int numsSize, int k){ k = numsSize - k % numsSize; int start = 0, current = 0, val = nums[0]; for (int i = 0; i < numsSize; i++) { int source = (current + k) % numsSize; if (source == start) { nums[current] = val; current = ++start; val = nums[start % numsSize]; } else { nums[current] = nums[source]; current = source; } } }