Do this in C++: 1. You should write a program to create a singly linked list. Th
ID: 3665345 • Letter: D
Question
Do this in C++:
1. You should write a program to create a singly linked list. The node in the list stores integers.
2. Create a list with 15 nodes (odd nodes). The list nodes will not store duplicate integers.
3. Traverse the list to print the number stored in each node. (recursive function).
4. Write a recursive function that prints the middle node of the list. In your case it would be the 8th node.
You do not assume there are 15 nodes. So you do not know the number of nodes in the list. The only thing you know is that
there are odd number of nodes (So there exists exactly one middle node).
You cannot count the number of nodes in the list.
YOU CANNOT USE GLOBAL VARIABLES OR STATIC VARIABLES etc.
The function can have at the most 2 arguments.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
/* This is the structure of a node */
struct node {
int data; //Data part
struct node *next; // this is the address part
}*head;
/* Functions to create and display list
*/
void createListone(int n);
void traverseListone();
int main()
{
int n;
cout<<"Enter the total number of nodes”;
cin>>n;
createListone(n);
cout<<” the data present in the list is “;
traverseListone();
return 0;
}
/* To Create a list of N nodes here
*/
void createList(int n)
{
struct node *newNode, *temp;
int data, i;
head = (struct node *)malloc(sizeof(struct node));
/* If we are unable to allocate the memory for the head node then
*/
if(head == NULL)
{
cout<<"Unable to allocate memory.";
}
else
{
/* Enter and reads data of a given node from the user
*/
cout<<” enter the data of the node one”;
cin>>data;
head->data = data; // It is used to link the data field with data
head->next = NULL; // It is used to link the address field to NULL
temp = head;
/* For creating n nodes and adding to the linked list we will
*/
for(i=2; i<=n; i++)
{
newNodeone = (struct node *)malloc(sizeof(struct node));
/* To check if the memory is allocated for newNodeone */
if(newNodeone == NULL)
{
cout<<” the memory is unable to be allocated”;
break;
}
else
{
cout<<” enter the data for node i”;
cin>data;
newNodeone->data = data; // It is used to link the data field of newNodeone with data
newNodeone->next = NULL; // It is used to link the address field of newNodeone with NULL
temp1->next = newNodeone; // It is used to links previous node i.e. temp to the newNodeone
temp1 = temp1->next;
}
}
}
}
/*
* Displays the entire list
*/
void traverseList()
{
struct node *temp1;
/* To see if the list is empty, If the list is empty i.e. head = NULL
*/
if(head == NULL)
{
Cout<<”the list is empty”;
}
else
{
temp1 = head;
while(temp1 != NULL)
{
cout<< temp1->data); //It is used to prints the data of current node
temp1 = temp1->next; // next it advances the position of current node
}
}
}
To find the middle node we will use this function
int FindMid(Node * head, int n = 0) /* n is the number of nodes*/
{
if( NULL == head )
{
return 0;
}
++ n;
int nNodeBackTraverced = FindMid(head->next, n);
if( (nNodeBackTraverced == (n - 1)) || (nNodeBackTraverced == n) )
cout << "Mid Node data: " << head->data << endl;
return ++nNodeBackTraverced;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.