Reversing a linked list using recursion in C
I'm new to C and I'm trying to create a function to modify a linked list by passing only the list itself as a parameter. Is it possible to do without passing node as a parameter?
Here is my code so far, I know it is not working correctly because I cannot figure out how to make a recursive call to 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;
}
It also contains type definitions.
typedef struct {
node_t *head;
node_t *tail;
} LL_t;
typedef struct _node {
int data;
struct _node *next;
} node_t;
source to share
You can reverse the list with a simple loop, no recursion is needed and you don't need your API.
Here's 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 need to use recursion, you can check if the pool is empty or the singleton is limited and do nothing, otherwise remove the head element, discard the resulting list and add 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 can have undefined behavior if the list is too long, as it reverse
will restart too many times and cause a stack overflow...
source to share
struct node {
int value;
struct node* next;
};
Non-recursive definition, working 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;
}
}
Externally 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;
}
This works, but using recursion to modify the list requires O (n) stack overhead. The concept here is to promote a static instance of L-> head while keeping a local copy of the head for each level of recursion. The recursion continues until the end of the list is reached, then the list will be reversed using local head instances since reverse () returns a fallback 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
}
source to share
// Simple program for changing 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;
}
source to share