C++ PROGRAM: Write a function called mergeLists that takes two call-by-reference

Question

C++ PROGRAM: Write a function called mergeLists that takes two call-by-reference arguments that are pointer variables that point to the heads of linked lists of values of type int. The two linked lists are assumed to be sorted so that the number at the head is the smallest number, the number in the next node is the next smallest, and so forth. The function returns a pointer to the head of a new linked list that contains all the nodes in the original two lists. The nodes in this longer list are also sorted from smallest to largest values. Note that your function will neither create nor destroy any nodes. When the function call ends, the two pointer variable arguments should have the value NULL. You may use the following code as a starting point.

class IntNode {

public: IntNode() {}

IntNode(int d, IntNode* n)

{ data = d; next = n;

}

IntNode* getNext() {

return next;

} int getData() {

return data;

}

void setNext(IntNode* n) {

next = n;

}

private: int data;

IntNode *next;

};

void addToList(IntNode* &list, int n) {

IntNode* current = list;

if (current == NULL) {

list = new IntNode(n, NULL);

return;

}

while (current->getNext() != NULL) {

current = current->getNext();

}

current->setNext(new IntNode(n, NULL));

}

void printList(IntNode *list3) {

while(list3 != NULL) {

cout<getData()<<" ";

list3 = list3->getNext();

}

cout<<endl;

}

int main() {

   IntNode *list1 = NULL;

   addToList(list1, 1);

   addToList(list1, 3);

   addToList(list1, 4);

   addToList(list1, 6);

   printList(list1);

   IntNode *list2 = NULL;

   addToList(list2, 2);

   addToList(list2, 3);

   addToList(list2, 7);

   printList(list2);

   IntNode* list3 = mergeLists(list1, list2);

   printList(list3);

   //Note that you might want to test your function with different cases to make sure the merging is correct

}

Explanation / Answer

Program:

#include <iostream>

Using namespace std;

Struct node

{

Int data;

Node *link;

};

Typedef node* NodePtr;

Void addToEnd(NodePtr& head, int val);

//Precondition: head has been initialized, val holds the value to add to the list.

//Postcondition: A new node containing val has been added to the end of the list.

Void printList(NodePtr head);

//Precondition: head has been initialized.

//Postcondition: The list has been printed to the standard output

NodePtr mergeLists(NodePtr& list1, NodePtr& list2);

//Precondition: The nodes in list1 and list2 contain values in increasing order

//Postcondition: Returns a list containing the ordered merge of list1 and list2;

//list1 and list2 are NULL

Int main()

{

Int nextInt;

//create two empty lists

NodePtr list1=NULL;

NodePtr list2=NULL;

//Put values in list1

Cout <<

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.