Hi, I need a merge method for this double linked list code, which A merge() method that merges the calling list with the parameter list in such a way that the result is a list that is sorted in ascending order and contains no duplicate values. The resulting list should be returned. The two original lists should be empty when the function exits (not destroyed). Method signature is provided and may not be changed. (already got other things to work, just need a merge method. Let me know if need more information)

Below is the main:

#include "DLinkedList.h"

#include

#include

#include

using namespace std;

string cleanUp(string str);

int main() {

DLinkedList lst1;

DLinkedList lst2;

ifstream fin("Text1.in");

string str;

while (fin>>str) {

str = cleanUp(str);

lst1.insertOrderUnique(str);

}

fin.close();

fin.open("Text2.in");

while (fin>>str) {

str = cleanUp(str);

lst2.insertOrderUnique(str);

}

cout << "List 1: " << lst1 << endl;

cout << "List 2: " << lst2 << endl;

DLinkedList combined = lst1.merge(lst2);

cout << " AFTER MERGE" << endl;

cout << "List 1: " << lst1 << endl;

cout << "List 2: " << lst2 << endl;

cout << " Combined: " << combined << endl;

return 0;

}

/**

* ASSIGNED

* @param str

* @return str in all lower case with LEADING and TRAILING non-alpha

* chars removed

*/

string cleanUp(string str) {

int starting = str.length();

int end = 0;

for (int i = 0; i < str.length(); i++) {

str[i] = tolower(str[i]);

if (str[i] >= 97 && str[i] <= 122) {

if (i < starting)

starting = i;

if (i > end)

end = i;

}

}

return str.substr(starting, end - starting + 1);

}

//below is the header file:

#pragma once

#include

using namespace std;

template < class T >

class DLinkedList {

//PROVIDED

friend ostream & operator << (ostream & out,

const DLinkedList < T > & rhs) {

DNode * curr = rhs.header -> next;

while (curr != rhs.header) {

out << curr -> data << " ";

curr = curr -> next;

}

return out;

}

public:

//inner class DNode PROVIDED

class DNode {

public:

DNode * next;

DNode * prev;

T data;

DNode(T val = T()) {

data = val;

next = prev = this;

}

};

//create an empty list: PROVIDED

DLinkedList() {

//create the header

header = new DNode();

}

//add method PROVIDED

DNode * add(T item) {

//add a new node and return a

//pointer to this node

DNode * newNode = new DNode(item);

newNode -> prev = header;

newNode -> next = header -> next;

header -> next -> prev = newNode;

header -> next = newNode;

return newNode;

}

/**

* ASSIGNED

* remove val from the list

*

* @param val

* @return true if successful, false otherwise

*/

bool remove(T val) {

DNode * curr = header->next;

while (val > curr->data && curr != header) {

curr = curr->next;

}

if (curr->data == val) {

DNode * prevNode = curr->prev;

DNode * nextNode = curr->next;

delete curr;

prevNode->next = nextNode;

nextNode->prev = prevNode;

return true;

}

return false;

}

/**

* ASSIGNED

*

* @param item

*/

void insertOrder(T item) {

DNode * newDNode = new DNode(item); // new node containing the new data

DNode * temp = header -> next; // temp header node

while (temp -> data <= newDNode -> data && temp != header) {

temp = temp -> next;

} // loop to know where to insert the new data

if (temp -> next == header && temp -> data <= newDNode -> data) { // checks if the data is less than the final node

newDNode -> next = temp -> next; // inserts node before the last value

newDNode -> prev = temp;

temp -> next -> prev = newDNode;

temp -> next = newDNode;

} else if (temp == header && temp -> data >= newDNode -> data) { // checks if the data is greater than the final node

newDNode -> next = temp; // inserts node after the last value

newDNode -> prev = temp -> prev;

temp -> prev -> next = newDNode;

temp -> prev = newDNode;

header = newDNode; // reassign header node

} else { // inserts node for all other cases

newDNode -> next = temp;

newDNode -> prev = temp -> prev;

temp -> prev -> next = newDNode;

temp -> prev = newDNode;

}

}

/** *

ASSIGNED

*

*

@param item */

bool insertOrderUnique(T item) {

DNode * newDNode = new DNode(item); // new node containing the new data

DNode * temp = header -> next; // temp header node

while (temp -> data <= newDNode -> data && temp != header) {

temp = temp -> next;

} // loop to know where to insert the new data

if (temp->prev->data == item) { ///// added this

return false;

}

if (temp -> next == header && temp -> data <= newDNode -> data) { // checks if the data is less than the final node

newDNode -> next = temp -> next; // inserts node before the last value

newDNode -> prev = temp;

temp -> next -> prev = newDNode;

temp -> next = newDNode;

} else if (temp == header && temp -> data >= newDNode -> data) { // checks if the data is greater than the final node

newDNode -> next = temp; // inserts node after the last value

newDNode -> prev = temp -> prev;

temp -> prev -> next = newDNode;

temp -> prev = newDNode;

header = newDNode; // reassign header node

} else { // inserts node for all other cases

newDNode -> next = temp;

newDNode -> prev = temp -> prev;

temp -> prev -> next = newDNode;

temp -> prev = newDNode;

}

return true;

}

//////////////merge should be below////////////////

/**

* ASSIGNED

* PRE: this and rhs are sorted lists

* @param rhs

* @return list that contains this and rhs merged into a sorted list

* POST: returned list will not contain duplicates, both rhs and this

* will have no elements

*/

DLinkedList merge(DLinkedList rhs) {

DLinkedList result;

return result;

}

private:

//DLinkedList fields: PROVIDED

DNode * header;

};

///////below is the text1.in file

Baby Face! You've got the cutest little Baby Face! There's not another one could take your place Baby Face

////////text2.in file

I'm bringing home a baby bumblebee, Won't my mommy be so proud of me, I'm bringing home a baby bumblebee, Won't my mommy be so proud of me, Ouch! It stung me! (spoken)