What is the best way to create/reverse a linked list? [closed]

Question

I'm a beginner at programming and I've learnt how to reverse a linked list. Below is the code I used to make a linked list with random values and reverse it. I was wondering what the best way to do this would be. Thanks for your suggestions! Have a great day!

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

// node
typedef struct node{
    int number;
    struct node *next;
}node;

// functions
node *reversedList(node *head);
void printList(node *head);
node *create(int size);

int main(void)
{
    srand(time(0));
    // ........
}

node *reversedList(node *curr)
{
    // a->b->c->d
    // d->c->b->a
    node *previous = NULL;
    while(curr->next != NULL)
    {
        node *curr_temp = curr->next;
        curr->next = previous;
        previous = curr;
        curr = curr_temp;
    }
    curr->next = previous;
    return curr;
}

void printList(node *head)
{
    if (head == NULL)
        return;
    printf("%d ",head->number);
    printList(head->next);
}

node *create(int size)
{
    if(size == 0)
        return NULL;
    node *n = malloc(sizeof(node));
    n->number = rand() % 10;
    n->next = create(size - 1);
    return n;   
}

Answer 1

Side note: Curiously, you did an iterative solution for reversal, but did a recursive solutions for create and printList

Your function is pretty close to optimal.

But, you fetched curr->next twice. Admittedly, with an optimizer, there should be no extra speed penalty.

But, I'd simplify that. And, I think a for loop can be cleaner:

node *
reversedFor(node *curr)
{
    // a->b->c->d
    // d->c->b->a
    node *prev = NULL;
    node *next;

    for (;  curr != NULL;  curr = next) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
    }

    return prev;
}

Edit: And, as Vlad mentioned, you don't check for curr being non-null before dereferencing it. So, my above refactoring fixed the bug with a bit of serendipity.

---

Here's what I'd to clean everything up:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// node
typedef struct node {
    int number;
    struct node *next;
} node;

// functions
node *reversedList(node *head);
node *reversedFor(node *head);
void printList(node *head,const char *tag);
node *create(int size);
node *delList(node *head);

typedef node *(revfnc_p)(node *head);

void
dotest(revfnc_p fnc,const char *tag)
{
    node *list;

    printf("dotest: %s\n",tag);

    list = create(10);
    printList(list,"orig");

    list = fnc(list);
    printList(list,"revd");

    delList(list);
}

int
main(void)
{

    dotest(reversedList,"reversedList");
    dotest(reversedFor,"reversedFor");

    return 0;
}

node *
reversedList(node *curr)
{
    // a->b->c->d
    // d->c->b->a
    node *previous = NULL;

    while (curr->next != NULL) {
        node *curr_temp = curr->next;

        curr->next = previous;
        previous = curr;
        curr = curr_temp;
    }
    curr->next = previous;
    return curr;
}

node *
reversedFor(node *curr)
{
    // a->b->c->d
    // d->c->b->a
    node *prev = NULL;
    node *next;

    for (;  curr != NULL;  curr = next) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
    }

    return prev;
}

void
printList(node *head,const char *tag)
{

    if (tag != NULL)
        printf("%s:",tag);

    for (node *curr = head;  curr != NULL;  curr = curr->next)
        printf(" %d",curr->number);

    printf("\n");
}

node *
create(int size)
{
    node *head = NULL;
    node *prev = NULL;
    node *curr;

    for (int idx = 0;  idx < size;  ++idx) {
        curr = malloc(sizeof(*curr));
        curr->number = idx;
        curr->next = NULL;

        if (head == NULL)
            head = curr;
        else
            prev->next = curr;

        prev = curr;
    }

    return head;
}

node *
delList(node *curr)
{
    node *next;

    for (;  curr != NULL;  curr = next) {
        next = curr->next;
        free(curr);
    }

    return curr;
}

---

Here's the program output:

dotest: reversedList
orig: 0 1 2 3 4 5 6 7 8 9
revd: 9 8 7 6 5 4 3 2 1 0
dotest: reversedFor
orig: 0 1 2 3 4 5 6 7 8 9
revd: 9 8 7 6 5 4 3 2 1 0