c program to print reverse of a linked list using recursion. for example if the given linked list is 0->1->2->NULL then the recursive function should print 2 1 0.

c program to print reverse of a linked list using recursion

#include<stdio.h>
#include<malloc.h>

typedef struct list_
{
	int data;
	struct list* next;
} list;

void append(list **head, int id);
list* create_node(int data);

void reverse_list(list* curr)
{
        // Base case
	if (curr == NULL) return;
	reverse_list(curr->next);
	printf("%d ", curr->data);
}

int main()
{
	list *head = NULL;
	//insert 0 ,1 and 2
	int i;
	for (i = 0; i < 3; i++)
	{
		append(&head, i);
	}
	reverse_list(head);
	printf("\n");
	return 0;
}

void append(list **head, int data)
{
	list *current = *head;
	// if the list is first node
	if (current == NULL)
	{
		current = create_node(data);
		(*head) = current;
		return;
	}

	// go to last node
	while (current->next != NULL)
		current = current->next;

	list* new_node = create_node(data);
	current->next = new_node;
}

list* create_node(int data)
{
	list* node = (list*) malloc(sizeof(list));
	node->data = data;
	node->next = NULL;
	return node;
}

How it works

void reverse_list(list* curr)
{
	if (curr == NULL) return;
	reverse_list(curr->next);
	printf("%d ", curr->data);
}
  • When the recursive function reverse_list() would unwind i.e returnĀ  , the curr pointer would point to last node.
  • So the statement just below the reverse_list() would print the linked list in reverse order.

The below animation of reverse of a linked list using recursion might help you to visualize the recursive calls.

 reverse of a linked list using recursion



Related Contents to follow