c++ linked list #include using namespace std; struct Node { int data; Node* next
ID: 3844735 • Letter: C
Question
c++ linked list
#include
using namespace std;
struct Node {
int data;
Node* next;
};
/* Task 1: Implement the following function for adding a new node to the
front of the given list with double the given value.
input Nodes* head: a head pointer to a list
int val: an integer that represent a value.
return the head pointer of the new list after the insertion
Example: add a node with given value 9
before HEAD->1->2->3->NULL
after HEAD->18->1->2->3->NULL
*/
Node* addDouble(Node* head, int val){
fill in here????
}
/* Task 2: Implement the following function for summing up the elements in
the even position of the given list. Assume the head node is in position 1.
input Nodes* head: a head pointer to a list
return void
output The sum of all elements in the even position of a given list
Example: input HEAD->1->2->3->9->12->NULL
output 11
(2+9=11)
*/
void sumEven(Node* head){
fill in here????
}
/* Task 3: Implement the following function for reversing the node with the
minimum value between Node n1 and Node n2.
input Nodes* n1: a pointer to a node in a list
Nodes* n2: a pointer to a node in the same list
return the node got removed which has the minimum value between the two
given nodes.
Example:
before HEAD->1->2->3->9->12->NULL
after HEAD->1->3->2->9->12->NULL
*/
Node* reverse(Node* n1, Node* n2){
fill in here??????
}
// You are not supposed to change the main function
int main() {
Node* head = NULL;
Node *p4, *p7;
for(int i = 1; i < 10; i++) {
head = addDouble(head, i);
if (i==4) p4 = head;
if (i==7) p7 = head;
}
// at this point, we have created the following list: HEAD->18->16->14->12->10->8->6->4->2->NULL
// p4 now points to node 4 (the node containing 8); p7 now points to node 7 (the node containing 14)
reverse(p4, p7);
// between p4 and p7, there are 2 nodes.
// The resulting list is HEAD->18->16->14->10->12->8->6->4->2->NULL
//You can uncomment this line to test.
//the output should be: 38
//Please remember to comment this line out before submitting
// cout <- sumEven(head);
head = addDouble(head, 16);
head = addDouble(head, 20);
// at this point, the list is: HEAD->40->32->18->16->14->10->12->8->6->4->2->NULL
reverse(p7, head);
// between p7 and head, there are 3 nodes (32, 18 and 16).
//The list after the function call is: HEAD->40->16->18->32->14->10->12->8->6->4->2->NULL
cout << sumEven(head);
// the output should be: 70
// free all nodes
Node* tmp;
while (head) {
tmp = head;
head = head->next;
delete tmp;
}
return 0;
}
Explanation / Answer
// Task 1
Node* addDouble(Node* head, int val){
//create temperory for old head and allocate space for new head
//initialize data members of new head that is data is twice of val
//and next pointer now points to old head then then assign head to new head and return
if(head == NULL){
Node *newHead = new Node;
newHead->data = 2*val;
newHead->next = NULL;
return newHead;
}
Node* oldHead = head;
Node* newHead = new Node;
newHead->data = 2*val;
newHead->next = oldHead;
head = newHead;
return head;
}
int sumEven(Node* head){
int sum=0;
Node* temp = head; //odd position
temp = temp->next; //now in even position
while(temp != NULL){
sum += temp->data;
if(temp!=NULL)temp->next;
if(temp!=NULL)temp->next; // two increment needed to make temp in next even position
}
return sum;
}
//Task3. Reversing two nodes assuming n1 came before n2 in list
// that is head-> .......->n1->...........->n2->......null
//we also need pointer to head which is neccessary
Node* reverse(Node* head, Node* n1, Node* n2){
//find node befor n1 and n2
Node* bef_n1;
Node* bef_n2;
while(true){
bef_n1 = head;
Node* temp = bef_n1;
bef_n1 = bef_n1->next;
if(bef_n1 == n1){
bef_n1 = temp; // temp is one position before n1
break;
}
}
while(true){
bef_n2 = head;
Node* temp = bef_n2;
bef_n2 = bef_n2->next;
if(bef_n2 == n2){
bef_n2 = temp; // temp is one position before n2
break;
}
}
// do the actual reversing of nodes
bef_n1->next = n2;
bef_n2->next = n1;
n1->next = n2->next;
n2->next = n1->next;
if(n1->data<n2->data) return n1;
return n2;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.