BugCrush 2 Question 4 - BUGC204 - EDITORIAL

editorial
,
1

BugCrush 2 Question 4 - BUGC204 - EDITORIAL

PROBLEM LINK

Practice
Contest

Author: codechefsrm
Editorialist : codechefsrm

DIFFICULTY

MEDIUM

PREREQUISITES

Linked List, Recursion

PROBLEM

Problem Description
Program to count the number of nodes in a linked list using recursion.

Input:
No Input

Output:
Count of nodes is 5

Rules:
Bugs will be mainly logical errors, syntax errors etc. They are specific to C language.
Since it is a debugging contest, you will be provided with a bugged solution below the Constraints section.
Please, see that you must adhere to the problem code provided, make changes only where necessary.
Participants can copy the code and compile it using an online compiler (Eg. CodeChef IDE).
Once the bugs are eliminated from the code, the clean code should be submitted by using the “Submit” button on the top-right corner.
Participants will be penalised for changing the entire problem solution or writing their own solution, completely different from the buggy code as provided in the
problem statement as our main intention is to test the debugging abilities of the participants.

Buggy Code in C
Please copy the following code and paste it into your compiler for debugging.

#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node next;
};
int count(struct Node* head)
{
if (head == NULL)
return 0;
return count(head->next);
}
void add(struct Node** header, int datum)
{
struct Node* point = (struct Node*) malloc(sizeof(struct Node));
point->data = datum;
datum->next = (*header);
(*header) = data;
}
int main()
{
struct Node head = NULL;
add(&head, 1);
add(&head, 3);
add(&head, 1);
add(&head, 2);
add(&head, 1);
printf("Count of nodes is %d", count(head));
return 0;
}

SOLUTION

#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node* next;
};
int count(struct Node* head)
{
if (head == NULL)
return 0;
return 1 + count(head->next);
}
void add(struct Node** header, int datum)
{
struct Node* point = (struct Node*) malloc(sizeof(struct Node));
point->data = datum;
point->next = (*header);
(*header) = point;
}
int main()
{
struct Node* head = NULL;
add(&head, 1);
add(&head, 3);
add(&head, 1);
add(&head, 2);
add(&head, 1);
 
printf("Count of nodes is %d", count(head));
return 0;
}

EXPLANATION

Iterative Solution

  1. Initialize count as 0
  2. Initialize a node pointer, current = head.
  3. Do following while current is not NULL
    a) current = current → next
    b) count++;
  4. Return count