Recursive Linked List Reversal Function in C

Question

My List is implemented via these two structs. The first contains the items in the list while the second contains the list itself.

typedef Employee Item;

typedef struct ListNodeTag {
    Item item;
    struct ListNodeTag *next;
} ListNode;

typedef struct {
    int size;
    ListNode *first;
} List;

I am trying to use the following recursive function to reverse the contents of the list however, I am getting a segmentation fault once there is more than one item in the list.

void Reverse(List *L){
  ListNode *q,*p;

  q = L->first;
  p = q->next;

  if(p == NULL)
    return;

  Reverse(L);

  q->next->next = q;
  q->next = NULL;}

I believe that the issue lies in the fact that instead of passing a member of the list as a function argument I am passing a pointer to the list itself. How would I change this code to let it work without passing a different argument?

possible duplicate of Linked list recursive reverse

Jonathan Leffler
– Jonathan Leffler

2013-11-04 23:30:08 +00:00
Commented Nov 4, 2013 at 23:30 — Jonathan Leffler
– Jonathan Leffler, Commented Nov 4, 2013 at 23:30

Shubham · Accepted Answer · 2013-11-05 08:56:43Z

You need to pass another parameter to the function to advance the recursive function to the end of the list. This can be done like this-

void Reverse(ListNode *f, List *l){
    if(l->first == NULL)
        return;

    //Last node reached
    if(f->next==NULL){
        l->first->next = NULL;
        l->first = f;
        return;
    }
    ListNode *p,*q;
    p = f;
    q = f->next;

    Reverse(f->next,l);

    q->next = p;
}

Though this function works, it takes a lot of memory, so I'd recommend an iterative approach, like this one-

void Reverse(List *l){
    ListNode *f = l->first;
    ListNode *fn,*fnn;

    if(f==NULL)
        return;
    fn = f->next;
    if(fn==NULL)
        return;
    fnn = fn->next;

    while(fnn!=NULL){
        fn->next = f;
        f = fn;
        fn = fnn;
        fnn = fnn->next;
    }
    fn->next = f;
    l->first->next = NULL;
    l->first = fn;
}

AAnderson · Accepted Answer · 2013-11-05 00:10:55Z

0

Have you made sure to initialise all your next pointers to NULL as you append items to the list?

Also, as I read it, the function won't actually recurse as you're always passing L. In other words, after the first call, how does the function know to go one further step down the list?

answered Nov 5, 2013 at 0:10

AAnderson

3711 gold badge3 silver badges4 bronze badges

Collectives™ on Stack Overflow

Recursive Linked List Reversal Function in C

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related