Thursday, September 29, 2022

Data Structures and Algorithms (Some Questions for You - Answer to Question 24) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

Let L1 be a singly linked list in memory. Write an algorithm

i) Finds the number of non-zero elements in L1

ii) Adds a given value K to each element in L1

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *link;
}*start;
void create(int);
void disp();
void count();
void main()
{
int ch,n,i,m,a,pos;
clrscr();
start=NULL;
do
{
printf(“\n\nMENU\n\n”);
printf(“\n1.CREATE\n”);
printf(“\n2.DISPLAY\n”);
printf(“\n3.COUNT\n”);
printf(“\n4.EXIT\n”);
printf(“\nENTER UR CHOICE\n”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“\n\nHOW MANY NODES U WANT TO CREATE\n”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(“\nENTER THE DATA”);
scanf(“%d”,&m);
create(m);
}
break;
case 3:
count();
break;
case 2:
disp();
break;
case 4:
exit(0);
}
}
while(ch!=4);
getch();
}
void count()
{
struct node *q;
int nonz=0,eno=0,ono=0;
q=start;
while(q!=NULL)
{
if(q->data>0)
{
nonz++;
}
if(q->data%2==0)
{
eno++;
}
else
{
ono++;
}

q=q->link;
}
printf(“\n\nPOSITVE NO ARE %d EVEN NO ARE %d ODD NO ARE %d”,nonz,eno,ono);
}

void create(int data)
{
struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=data;
tmp->link=NULL;
if(start==NULL)
{
start=tmp;
}
else
{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}
void disp()
{
struct node *q;
if(start==NULL)
{
printf(“\n\nLIST IS EMPTY”);
}
else
{
q=start;
while(q!=NULL)
{
printf(“%d->”,q->data);
q=q->link;
}
printf(“NULL”);
}
}

The idea is to solve this problem using the basic algorithm for the addition of two numbers. But since the given list is singly linked, we can’t iterate it in the backward direction. Therefore, to facilitate the addition, we can reverse the list.

We start by adding the given single-digit number to the digit at the first node in the reversed list. If the resultant sum is a 2-digit number, update the node with a single-digit sum and move the carry to the next node. This process is repeated while there is a carry. If we reach the last node and a carry exists, add a new node at the end of the linked list with carry as the value. Finally, reverse the list again to restore the original order.

The algorithm can be implemented as follows in C, Java, and Python:


Download  Run Code

Output:

Original linked list: 9 —> 9 —> 9 —> 9 —> 3 —> NULL
Resultant linked list: 1 —> 0 —> 0 —> 0 —> 0 —> 0 —> NULL

The time complexity of the above solution is linear, but the code performs several traversals of the linked list.

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds