typedef struct llnode{ int val ; struct llnode * nxt ; } llnode ; llnode* newNod
ID: 3784868 • Letter: T
Question
typedef struct llnode{
int val ;
struct llnode * nxt ;
} llnode ;
llnode* newNode( int val ){
llnode myguy= (llnode*) malloc(sizeof(llnode));
myguy->val=val;
myguy->nxt= NULL;
return myguy;
}
llnode* pushFront( llnode* head, llnode* push){
push->nxt = head;
return push;
}
llnode *pushBack( llnode* head, llnode* push){
llnode* tmp;
tmp = head;
while (tmp!= NULL){
tmp = tmp ->nxt;
}
tmp-> nxt = push;
return head;
}
llnode *arr2ll( int arr[] , int size ){
}
llnode *insert( llnode *head, llnode *ins, int loc){
}
FILL IN THE LAST PARTS OF THIS CODE... implement getMedian to return the median of the array
Explanation / Answer
Program returns median of an array.
//Added an additional print method to print the list + minor corrections in the existing code
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct llnode{
int val ;
struct llnode * nxt ;
} llnode ;
llnode* newNode( int val ){
//Correction: myguy should be pointer
llnode* myguy= (llnode*) malloc(sizeof(llnode));
myguy->val=val;
myguy->nxt= NULL;
return myguy;
}
llnode* pushFront( llnode* head, llnode* push){
push->nxt = head;
return push;
}
llnode *pushBack( llnode* head, llnode* push){
llnode* tmp;
tmp = head;
//Correction-> check tmp->next!=NULL
while (tmp->nxt!= NULL){
tmp = tmp ->nxt;
}
tmp->nxt = push;
return head;
}
llnode *arr2ll( int arr[] , int size ){
//Creating head node
llnode* head = newNode(arr[0]);
for(int i=1;i<size;i++){
llnode* push = newNode(arr[i]);
//Pushing subsequent nodes in the list
pushBack(head,push);
}
//Returning pointer location of head node
return head;
}
// Assuming loc as location in array
llnode *insert( llnode *head, llnode *ins, int loc){
llnode* tmp;
tmp = head;
//Already at loc 0 so iterating from 1 to loc-1
for(int i=1;i<loc;i++){
tmp=tmp->nxt;
}
ins->nxt = tmp->nxt;
tmp->nxt = ins;
return head;
}
int getMedian(llnode *head,int size){
int median;
if(size%2==0){
median = size/2;
}
else{
median = size/2 + 1;
}
llnode* tmp = head;
//Already at first node = head
median--;
while(median!=0){
tmp = tmp->nxt;
median--;
}
return tmp->val;
}
void print(llnode *head){
llnode* tmp = head;
while(tmp!=NULL){
cout<<tmp->val<<" ";
tmp=tmp->nxt;
}
}
int main(){
int arr[] = {2,3,4,1,5};
int size = 5;
//Creating list from array
llnode* head = arr2ll(arr,size);
//Printin array
print(head);
//Printing median of array
cout<<" Median of array: "<<getMedian(head,size);
//Inserting a new node
llnode* ins = newNode(7);
insert(head,ins,4);
//Updating size
size++;
cout<<" ";
//Printing new list
print(head);
//Printing new median
cout<<" Median of array: "<<getMedian(head,size);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.