CODEWITHSUNDEEP
calgorithmlinked-list
baskon1
baskon1

Reputation: 330

Recursive Algorithm for Linked List in C

I have a structure which I name passengers, which is sorted in alphabetical order, and I copy it to a linked list with the same elements as structure. What would be the best algorithm to reverse the order of the elements of the list, so that I can print it out in alphabetical order easily? Now of course my printing doesn't work if the first value it encounters is NULL

typedef struct               
{
    char fullname[40];
    unsigned short phonenr[10]; 
    unsigned int seatnr;        
}PASSENGERS;       


typedef struct list1
{
    char fullname[40];
    struct list1 *next;
}LIST1;

int main()
{
    selectsortnm(passenger); /*A function I use to sort alphabetically*/
    LIST1 *list1, *start=NULL;
    int i=0;
    while (strcmp(passenger[i].fullname,"\0")!=0);
    {
        list1 = (LIST1 *) malloc (sizeof(LIST1));
        list1->next = NULL;
        strcpy(list1->fullname,passenger[i].fullname);
        if (start ==NULL)
        {
            start = list1;
            i++;
        }
        else 
        {
            list1->next = start;
            start = list1;
            i++;
        }
    }

    //Recursive algorithm

    LIST1 *current = list1;
    while (current !=NULL)
    {
        printf("%s",current->fullname);
        current = current->next;
    }
}

Upvotes: 0

Views: 220

Answers (2)

jxh
jxh

Reputation: 70392

You do not need a recursive algorithm to reverse your list. You can just change how you are inserting into your list.

This is how you are inserting items into your list:

        list1 = make_list_item_from(passengers[i]);
        list1->next = start;
        start = list1;
        i++;

Assuming passengers is sorted, inserting at the front of the list results in a list that is in reverse of the order of passengers.

To counter this, you can walk passengers backwards as you insert into your list. Alternatively, you can maintain a reference to the last item of the list, and add your new items to the end of your list.

Upvotes: 1

Paul Ogilvie
Paul Ogilvie

Reputation: 25286

Assuming a singly linked list, indeed recursive traversal will print it in reverse order...if the stack has enough space of course:

void printListRev(struct LIST *p)
{
    if (!p) return;
    printListRev(p->next);
    printf("%s\n", p->data);
}

Upvotes: 1

Related Questions