Merge two Linked ordered linked list

Hi,

I am trying to implement a mergelist function that combines the elements in list1 and list 2 into a single list.I have derived the orderedLinkedList from the base class linkedlist .. I am having issues with the merge list.. Can anyone help me..


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
# include <iostream>
using namespace std;
#include<assert.h>

struct Node
{
	int info;
	Node* link;
};

class LinkedList
{
	protected:
     	Node *first;
    	Node *last;
    	int count;
	public:
       LinkedList();
       void insertbeg(int newItem);
       const LinkedList& operator=(const LinkedList&) ;
       void copyList(const LinkedList& otherList) ;
       void print() ;
       void insertend(int newItem);
       void deleteNode(int deleteItem);
       void buildListForward();
       int front() const;
       ~LinkedList();
       void traverse_and_print();
       void destroyList();
};

const LinkedList& LinkedList:: operator= (const LinkedList& otherList)
{
   if (this != &otherList) //avoid self-copy
   {
       copyList(otherList) ;
    }//end else
   return * this;
}

void LinkedList :: copyList(const LinkedList& otherList)
{
	Node  *newNode = new Node; //pointer to create a node
	Node *current; //pointer to traverse the list
	if (first != NULL) //if the list is nonempty, make it empty
		destroyList() ;
	if (otherList. first == NULL) //otherList is empty
	{
		first = NULL;
		last = NULL;
		count = 0;
	}else
	{
		//first copy the first node
		current = otherList. first; //current points to the list to be copied
		count = otherList. count;//copy the first node
		first = new Node; //create the node
		first->info = current->info; //copy the info
		first->link = NULL; //set the link field of the node to NULL
		last = first; //make last point to the first node

		//copy the remaining list
		current = current->link; //make current point to the next node
        while (current != NULL)
        {
        	newNode = new Node; //create a node
        	newNode->info = current->info; //copy the info
        	newNode->link = NULL; //set the link of newNode to NULL
        	last->link = newNode; //attach newNode after last
        	last = newNode; //make last point to the actual last node
        	current = current->link; //make current point to the next node
        }//end while
	}//end else
}//end copyList




LinkedList::LinkedList()
{
       first = last = NULL;
       count = 0;
}

void LinkedList::destroyList()
{
	Node * temp;
    while (first != NULL)
    {
    	temp = first; //set temp to the current node
    	first = first->link; //advance first to the next node
    	delete temp; //deallocate the memory occupied by temp
    }
	last = NULL; //initialize last to NULL; first has already been set to NULL by the while loop
	count = 0;

}

LinkedList::~LinkedList()
{
	destroyList();
}

int LinkedList :: front() const
{

return first->info; //return the info of the first node
}//end


void LinkedList::print()
{
	Node * current; //pointer to traverse the list
	current = first; //set current point to the first node
	while (current != NULL) //while more data to print
	{
	cout << current->info << " ";
	current = current->link;
	}
}


/*
int linkedListType :: length()
{
   return count;
}
*/

void LinkedList :: insertbeg(int newitem)
{

  Node *newNode = new Node;
  if (first == NULL)
  {
     newNode->info = newitem;
     newNode->link = NULL;
     first = newNode;
     last = newNode;
  }
}

void LinkedList :: insertend(int newitem)
{
  Node *newNode = new Node;
  newNode->info = newitem;
  newNode->link = NULL;
  last->link = newNode;
  last = newNode;
}

void LinkedList :: buildListForward()
{
	int num;
	cout << "Enter a list of integers ending with -999. "<< endl;
	cin >> num;
	first = NULL;
	while (num != -999)
	{
		Node *newNode = new Node;
		newNode->info = num;
		newNode->link = NULL;
		if (first == NULL)
		{
			first = newNode;
			last = newNode;
		}else
		{
			last->link = newNode;
			last = newNode;
		}
		cin >> num;
	}

}
///////////////////////////////////////////////////////////////

class orderedLinkedList: public LinkedList
{
public:
	bool search(const int& searchItem) const; // have code

	void insert(const int& newItem) ;

	void insertFirst(const int& newItem) ; // have code

	void insertLast(const int& newItem) ; //have code

	void deleteNode(const int& deleteItem) ; // have code

	orderedLinkedList& mergeLists(orderedLinkedList &list1, orderedLinkedList &list2) ;
	void print1();
	void MoveNode(struct node** destRef, struct node** sourceRef);

};

void MoveNode(struct Node** destRef, struct Node** sourceRef)
{
  /* the front source node  */
  struct Node* newNode = *sourceRef;
  assert(newNode != NULL);

  /* Advance the source pointer */
  *sourceRef = newNode->link;

  /* Link the old dest off the new node */
  newNode->link = *destRef;

  /* Move dest to point to the new node */
  *destRef = newNode;
}

void orderedLinkedList::print1()
{
	Node * current; //pointer to traverse the list
	current = first; //set current point to the first node
	while (current != NULL) //while more data to print
	{
	cout << current->info << " ";
	current = current->link;
	}
}


bool orderedLinkedList::search(const int& searchItem) const
{
	bool found = false;
	Node * current; //pointer to traverse the list
	current = first; //start the search at the first node
	while (current != NULL && found == false)
	{
		if (current->info >= searchItem)
			found = true;
		else
			current = current->link;
	}
	if (found)
		found = (current->info == searchItem) ; //test for equality
	return found;
}//end search


orderedLinkedList& orderedLinkedList:: mergeLists(orderedLinkedList &list1,orderedLinkedList &list2 )
{
	Node  * dummy = new Node; //pointer to create a node
    Node *tail;
    tail = dummy;

	dummy->link = NULL;
	while(1)
	{
		if (list1 == NULL)
	    {
	    /* if either list runs out, use the other list */
			tail->link = list2;
	        break;
	    }
	    else if (list2 == NULL)
	    {
	    	tail->link = list1;
	    	break;
	    }

		if (list1->info <= list2->info)
	    {
	       MoveNode(&(tail->link), &list1);
	    }
	    else
	    {
	       MoveNode(&(tail->link), &list2);
	    }
	    tail = tail->link;
	 }
	 return(dummy->link);
}


void orderedLinkedList :: insert(const int& newItem)
{
	Node * current; //pointer to traverse the list
	Node * trailCurrent; //pointer just before current
	Node * newNode; //pointer to create a node
	bool found;
	newNode = new Node; //create the node
	newNode->info = newItem; //store newItem in the node
	newNode->link = NULL; //set the link field of the node to NULL
	if (first == NULL) //Case 1
	{
		first = newNode;
		last = newNode;
		count++;
	}else
	{
		current = first;
		found = false;
		while (current != NULL && ! found) //search the list
		{
			if (current->info >= newItem)
				found = true;
			else
			{
				trailCurrent = current;
				current = current->link;
			}
	    }
		if (current == first) //Case 2
		{
			newNode->link = first;
			first = newNode;
			count++;
		} else //Case 3
		{
			trailCurrent->link = newNode;
			newNode->link = current;
			if (current == NULL)
			{
				last = newNode;
			}
			count++;
		}
	} //end else
}//end insert 
Last edited on
What issues do you have?
Registered users can post here. Sign in or register to post.