reverse_linked_list_rec.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
  int data;
  struct Node * next;
} Node;

Node * create_node(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * new_node  = (Node *)malloc(sizeof(Node));
	new_node->data = data;
	new_node->next = *headRef;
	*headRef  = new_node;
}

void print_list(Node * head){
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}

Node * reverse_linked_list_rec(Node * head){
	//If there are no node in linked list, just return
	if(!head) return head;
	
	//There is only one node in list, return that node.
	if(!(head->next)) return head;
	
	/*
	 Above two conditions can be written as 
         if(!head || !(head->next)) return head;
        */
	
	/*
	In this step, we are removing the first node, i.e head and 
	reverse the remaining list 
	Also, when fist time return from recusive call, it will be the last 
	node of linked list and that will be the head of reversed list.
	We will successively return the same head to upper calling function.
	*/
	Node * new_head = reverse_linked_list(head->next);
	/*
	Removed node, here head node should be added to end of list.
	It can be seen that last node in reversed list will next node of head.
	Keep in mind we are relying on the fact that removed_node->next is not 
	null in any case.In implementation take care to this fact. If this is 
	violated, we may end up getting null pointer exception 
	*/
	head->next->next = head;
	head->next  = NULL;
	
	return new_head;
}

int main(void) {
	
	Node * head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 7);
	
	printf("\n Original list :");
	print_list(head);
    	head = reverse_linked_list_rec(head);
    	printf("\n Reverse list :");
    	print_list(head);	
	
	return 0;
}