Find the length of a linked list using recursion

In this article, we are going to see how to write a recursive function to find the length of a linked list using C program?
Submitted by Piyas Mukherjee, on January 24, 2019

Solution:

Recursive function: func_length(node *temp)

Input:

A singly linked list whose address of the first node is stored in a pointer, say head.

Output:

Length of the link list

Data structure used:

Singly linked list where each node contains a data element say data, and the address of the immediate next node say next, with head holding the address of the first node.

Steps:

Declare a global variable l=0

Pseudo code:

Begin
	If(temp=NULL)
		print l //printing final length
	Else
		l=l+1;
		length(temp->next); //recursive call
	End If-else
End

C code:

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

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

//global variable to store length
int l=0; 

int main()
{
	node *head=NULL,*temp,*temp1;
	int len,choice,count=0,key;
	//building the link list 
	do
	{
		temp=(node *)malloc(sizeof(node));
		if(temp!=NULL)
		{
			printf("\nEnter the element in the list : ");
			scanf("%d",&temp->data);
			temp->next=NULL;
			if(head==NULL)
			{	
				head=temp;
			}
			else
			{
				temp1=head;
				while(temp1->next!=NULL)
				{
					temp1=temp1->next;
				}
				temp1->next=temp;
			}
		}
		else
		{
			printf("\nMemory not avilable...node allocation is not possible");
		}
		printf("\nIf you wish to add m ore data on the list enter 1 : ");
		scanf("%d",&choice);
	}while(choice==1);
	
	len=length(head);
	printf("The list has a total of %d no of nodes",l);
	
	return 0;
}

//recursive function to find length
int length(node *temp)  
{
	if(temp==NULL)
		return l;
	else
	{
		l=l+1;
		length(temp->next);
	}
}

Output

Enter the element in the list : 1

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 2

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 3

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 4

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 5

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 6

If you wish to add m ore data on the list enter 1 : 0
The list has atotal of 6 no of nodes