Reversing a Linked List using recursion in C

Question

I'm fairly new to C and I am trying to create a function to reverse a linked list, passing only the List itself as a parameter. Is this possible to do without passing a node as a parameter?

Here is my code so far, I know it does not work correctly because I cannot figure out how to make the recursive call on the rest of the list.

void reverse(LL_t *L) {
    if (L->head->next == NULL) {
        return;
    }

    node_t *rest = L->head->next;
    reverse(rest);
    node_t *q = rest->next;
    q->next = rest;
    rest->next = NULL;
}

As well here are my type definitions.

typedef struct {
    node_t *head;
    node_t *tail;
} LL_t;

typedef struct _node {
    int data;
    struct _node *next;
} node_t;

Write another function (not exposed in the API) that does the reversal from a node. — molbdnilo
– molbdnilo, Commented Mar 23, 2017 at 19:33
reverse(rest); type isn't match. reverse require LL_t* but type of rest is node_t*. — BLUEPIXY
– BLUEPIXY, Commented Mar 23, 2017 at 19:55
@BLUEPIXY I'm not sure how to make 'rest' into LL_t* so that it contains all elements except for the current head — Newbie18
– Newbie18, Commented Mar 23, 2017 at 20:03
It is not necessary to make it a recursive call, but for recursive calls, LL_t is just a holder, so it makes sense to use the node_t as a parameter. — BLUEPIXY
– BLUEPIXY, Commented Mar 23, 2017 at 20:06
Rather than making reverse itself a recursive function, what about supplementary functions (E.g void reverse_aux(LL_t*, node_t*) etc.) as recursive functions? — BLUEPIXY
– BLUEPIXY, Commented Mar 23, 2017 at 20:15

chqrlie · Accepted Answer · 2017-03-24 14:46:28Z

You can reverse the list with a simple loop, recursion is not needed and given your API, not appropriate.

Here is a modified version of your function:

void reverse(LL_t *L) {
    node_t *prev = NULL;
    node_t *curr = L->head;
    L->tail = curr;
    while (curr != NULL) {
        node_t *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    L->head = prev;
}

If you are required to use recursion, you can test if the list is empty or limited to a singleton and do nothing, otherwise remove the head element, reverse the resulting list and append the element to the end:

void reverse(LL_t *L) {
    if (L->head != L->tail) {
        /* at least 2 elements */
        node_t *node = L->head;
        L->head = node->next;
        node->next = NULL;
        reverse(L);
        L->tail = L->tail->next = node;
    }
}

Note that this recursive approach may have undefined behavior if the list is too long as reverse will recurse too many times and cause a stack overflow.

score 1 · Accepted Answer · 2017-09-27 22:26:17Z

1

struct node {
   int          value;
   struct node* next;
};

Non-recursive definition operating in constant stack space:

void reverse(struct node** ptr) {
   struct node* prev_ptr;
   struct node* node_ptr;

   if (prev_ptr = * ptr) {
      node_ptr = prev_ptr -> next;

      prev_ptr -> next = NULL;

      while (node_ptr) {
         struct node* temp = node_ptr -> next;

         node_ptr -> next = prev_ptr;

         prev_ptr = node_ptr;
         node_ptr = temp;
      }

      * ptr = prev_ptr;
   }
}

Extensionally equivalent recursive definition:

void reverse(struct node** ptr) {
   struct node* node_ptr;

   if (node_ptr = * ptr) {
      node_ptr -> next = NULL;

      * ptr = reverse_rec(node_ptr, node_ptr -> next);
   }
}

struct node* reverse_rec(struct node* prev_ptr, struct node* node_ptr) {
   if (! node_ptr) { return prev_ptr; }

   struct node* temp = reverse_rec(node_ptr, node_ptr -> next);
   node_ptr -> next = prev_ptr;
   return temp;
}

edited Sep 27, 2017 at 22:26

answered Mar 23, 2017 at 23:15

user6428287

3 Comments

rcgldr Over a year ago

Where does reverse() update list.tail? Where is the recursion (problem statement requires recursion)?

user6428287 Over a year ago

@rcgldr In its body? As in the answer: recursion doesn't make sense here.

user6428287 Over a year ago

@rcgldr Now look at it: it's horrible.

rcgldr · Accepted Answer · 2017-03-27 02:09:41Z

0

This works, but using recursion to reverse a list requires O(n) stack space overhead. The concept here is to advance the static instance of L->head, while keeping a local copy of head for each level of recursion. Recursion continues until the end of the list is reached, then the list is reversed using the local instances of head as reverse() returns backup the call chain.

void reverse(LL_t *L)
{
node_t *head;
    if(L->head == NULL || L->head->next == NULL)
        return;
    head = L->head;
    L->head = head->next;
    reverse(L);
    head->next->next = head;   // reverse the nodes
    head->next = NULL;
    L->tail = head;            // ends up setting tail to what was 1st node
}

edited Mar 27, 2017 at 2:09

answered Mar 24, 2017 at 0:22

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Comments

Shivam Singh · Accepted Answer · 2017-04-20 13:48:15Z

0

//A simple program to reverse a Linked List

void reverse(struct node* head_ref) { struct node* first;

struct node* rest;
if (head_ref == NULL)
   return; 

first = head_ref;  
rest  = first->next; 
if (rest == NULL)
   return;   

reverse(rest); 
first->next->next  = first;      
first->next  = NULL;          
head_ref = rest;

}

answered Apr 20, 2017 at 13:48

Shivam Singh

112 bronze badges

Collectives™ on Stack Overflow

Reversing a Linked List using recursion in C

4 Answers 4

Comments

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related