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
– Vlad from Moscow, Commented Feb 15, 2021 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
– 001, Commented Feb 15, 2021 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. — user14215102
– user14215102, Commented Feb 15, 2021 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
– Vojtie, Commented Feb 15, 2021 at 14:07
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? — 001
– 001, Commented Feb 15, 2021 at 15:12

001 · Accepted Answer · 2021-02-15 14:52:58Z

1

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);
}

edited Feb 15, 2021 at 14:52

answered Feb 15, 2021 at 14:18

001

13.6k5 gold badges38 silver badges72 bronze badges

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

6 Comments

Vojtie Over a year ago

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 Over a year ago

the whole point is about saving pointers in an array/dynamic memory

001 Over a year ago

@Vojtie Ok. I didn't get that. See updated answer.

001 Over a year ago

@Vojtie No, notice I changed the definition to list **s as it should be an array of list * and not an array of int *.

Vojtie Over a year ago

ohh okay, I didn't notice it. Thanks! It really makes sense now.

|

Collectives™ on Stack Overflow

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

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related