Recursive Algorithm for Linked List in C

Question

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

Your question is not clear. Also what is LIST1 ? Please share code that can be understood easily. — Surajeet Bharati
– Surajeet Bharati, Commented Dec 21, 2016 at 17:08
We need a linked-list.stackoverflow.com so we can filter out half of the incoming questions. — Dellowar
– Dellowar, Commented Dec 21, 2016 at 17:10
Using a doubly linked list would do the trick by traversing it backwards. Also (this is more like workaround) you could traverse the passengers array backwards when creating the list, but you would need 2 loops: 1 to get last index (the last record whose fullname is not NULL), and the 2nd: looping from the index found by previous loop to 0. Hmm, but there's recursivity in neither 2 approaches. — CristiFati
– CristiFati, Commented Dec 21, 2016 at 17:11
Thanks for the comments everyone, I am pretty new at this, but no excuses for this.. — baskon1
– baskon1, Commented Dec 21, 2016 at 17:16

Paul Ogilvie · Accepted Answer · 2016-12-21 17:46:31Z

1

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

answered Dec 21, 2016 at 17:46

Paul Ogilvie

25.3k4 gold badges25 silver badges43 bronze badges

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

Comments

jxh · Accepted Answer · 2016-12-21 17:56:45Z

1

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.

answered Dec 21, 2016 at 17:56

jxh

70.8k8 gold badges116 silver badges204 bronze badges

Collectives™ on Stack Overflow

Recursive Algorithm for Linked List in C

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related