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:
- C
- Java
- Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | #include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to create a new node of the linked list struct Node* newNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } // Helper function to print a given linked list void printList(char *msg, struct Node* head) { printf("%s", msg); while (head) { printf("%d —> ", head->data); head = head->next; } printf("NULL\n"); } // Function to reverse a given linked list void reverse(struct Node** head) { struct Node* prev = NULL; struct Node* current = *head; struct Node* next; // traverse the list while (current) { // tricky: note the next node next = current->next; // fix the current node current->next = prev; // advance the two pointers prev = current; current = next; } // fix the head pointer to point to the new front *head = prev; } // Function to add a single-digit number to a singly linked list // whose nodes represent digits of a number void addDigit(struct Node** head, int digit) { // empty list if (*head == NULL) { *head = newNode(digit); return; } // reverse the linked list reverse(head); // initialize carry with the given digit int carry = digit; // traverse the reversed list struct Node* curr = *head; while (carry) { // get a sum of the current node and carry int sum = curr->data + carry; // update value of the current node with the single-digit sum curr->data = sum % 10; // set carry for the next node carry = sum / 10; // break if the current node is the last if (curr->next == NULL) { break; } // move to the next node curr = curr->next; } // add a new node at the end of the linked list if there is any carry left if (carry) { curr->next = newNode(carry); } // reverse the list again to restore the original order reverse(head); } int main(void) { struct Node* head = newNode(9); head->next = newNode(9); head->next->next = newNode(9); head->next->next->next = newNode(9); head->next->next->next->next = newNode(3); int digit = 7; printList("Original linked list: ", head); addDigit(&head, digit); printList("Resultant linked list: ", head); return 0; } |
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
