Problem with implementing a function to reverse a linked list in C

Question

So I wanted to write a function to reverse a linked list using an array of pointers but I'm getting warnings: assignment from incompatible pointer type [-Wincompatible-pointer-types]. I wanted to store the pointers to nodes of the list in an array of pointers int **s = (int **)calloc(10, sizeof(int)); and thought that s[*top] = *l will assign the pointer to which **l is pointing to *topth element of array *s[]. So am I wrong thinking that elements of array *s[] are pointers? If someone could explain it to me I'd be very glad. Here's the whole code (except the part where I create the list which is fine):

typedef struct list {
    int v;
    struct list *next;
} list;

void reverseListS(list **l, int **s, int *top) {
    while ((*l)->next != NULL) {
        s[*top] = *l;
        *top++;
        *l = (*l)->next;
    }
    list *temp = *l;
    while (!(*top == 0)) {
        temp->next = s[*top];
        *top--;
        temp = temp->next;
    }
    temp->next = NULL;
}

int main() {
    int **s = (int **)calloc(10, sizeof(int));
    int *top = 0;

    reverseListS(&l, s, top);
}

The presented code does not make a sense. For example instead of int **s = (int **)calloc(10, sizeof(int)); you should at least write int **s = (int **)calloc(10, sizeof(int *)); — Vlad from Moscow, Feb 15 '21 at 13:49
Many issues. Just in `main`: Should be `sizeof(int *)` (or `sizeof *s`). Although, I think you want `s` to be an array of ints, so it should be an `int *`. And `top` does not point anywhere - why is it even a pointer?. `l` is not initialized.... — 001, Feb 15 '21 at 13:59
You should probably start with a simpler piece of code, let's say populating a list and printing it. Once that's working, add more complexity. Untangling this code is not feasible, throw it out and start over. — , Feb 15 '21 at 14:03
@JohnnyMopp I said I skipped initializing `list *l`, I can edit it. I thought that there is not difference between `sizeof(int *)` and `sizeof(int)` since amount of bytes used to store an integer is the same as a pointer to integer (correct me if im wrong). I made `top` a pointer so that changing its value inside the function will affect it outside too. if `s` would be an array of ints could I assign a pointer to a value stored in that array? because I tried to do that and it didnt work and googled that you can't realy point a pointer to an address stored in an integer variable. — Vojtie, Feb 15 '21 at 14:07
@dratenik I have done it already and it all works just fine, also wrote a function to reverse a list but wanted to do this using stack and encountered some problems, so I tried to do this just with using array of pointers. — Vojtie, Feb 15 '21 at 14:10
@Vojtie They may be the same, but might not. [Size of int and sizeof int pointer on a 64 bit machine](https://stackoverflow.com/a/20721311) — 001, Feb 15 '21 at 14:18
Using an array to reverse a list is not necessarily efficient, because you have to guess the size of the list. If you can accept to replace the old list with the new one (ie lose the initial list), it is much simpler to add every element before its predecessor... — Serge Ballesta, Feb 15 '21 at 14:31
@SergeBallesta I know it's not efficient, I'm just trying to understand how to do this as an exercise — Vojtie, Feb 15 '21 at 14:35
Then you should give us a [mcve]. I can more easily debug a code if I can run it on my own system... — Serge Ballesta, Feb 15 '21 at 14:53
@JohnnyMopp thanks, for the record - may there be a difference between sizeof(int*) and sizeof(int**) etc? — Vojtie, Feb 15 '21 at 15:09
Often, pointer sizes are the same regardless of type, but that is not guaranteed. [Are all data pointers the same size in one platform for all data types?](https://stackoverflow.com/a/1241314) — 001, Feb 15 '21 at 15:12

001 · Accepted Answer · 2021-02-15T14:52:58.830

Many issues. Just in main: Should be sizeof(int *) (or sizeof *s). Although, I think you want s to be an array of ints, so it should be an int *. And top does not point anywhere - why is it even a pointer?. l is not initialized.

In reverseListS at s[*top] = *l; you are trying to assign a struct list * to an int *.

I have re-written your code to work. I'm not saying this is the best way to reverse a list, but it makes the fewest modifications to your code - as I understand it.

typedef struct list {
    int v;
    struct list *next;
} list;

void reverseListS(list **l)
{
    // Count number of items
    //   *this step could be skipped by dynamically resizing the array with realloc
    int count = 0;
    list *temp = *l;
    while (temp) {
        count += 1;
        temp = temp->next;
    }
    // Allocate memory - an array of list *
    list **s = malloc(count * (sizeof *s));
    if (!s) return;
    // Copy list item addresses to array
    temp = *l;
    int index = 0;
    while (temp) {
        s[index++] = temp;
        temp = temp->next;
    }
    // Rebuild the list in reverse order
    //   *if you already have an "append_to_list" function, that should be used here
    temp = NULL;
    for (int i = index - 1; i >= 0; i--) {
        if (!temp) {
            // This is the new first item in list.
            // Make the original list point to it
            *l = temp = s[i];
        }
        else {
            // Append to end of new list
            temp->next = s[i];
            temp = s[i];
        }
        s[i]->next = NULL;
    }
    free(s);
}
int main() {
    list *l;
    // TODO: Fill the list with values.
    reverseListS(&l);
}

No that's not what I wanted to do, this is trivial. I wanted to make an array of pointers to store the addresses of nodes of the list so: at first travel the list to the end while copying address of each node to that array, then travel back the list while changing the links between nodes using that array of pointers. (something I've seen done using stack in c++, but didn't find it in C and tried at first to do this like that) — Vojtie, Feb 15 '21 at 14:27
the whole point is about saving pointers in an array/dynamic memory — Vojtie, Feb 15 '21 at 14:29
"In `reverseListS at s[*top] = *l`; you are trying to assign a `struct list * to an int *`" and aren't you doing the same there? `s[index++] = temp;` thanks btw. — Vojtie, Feb 15 '21 at 15:01
@Vojtie No, notice I changed the definition to `list **s` as it should be an array of `list *` and not an array of `int *`. — 001, Feb 15 '21 at 15:02
ohh okay, I didn't notice it. Thanks! It really makes sense now. — Vojtie, Feb 15 '21 at 15:05

Problem with implementing a function to reverse a linked list in C

1 Answers1