fork download
copy 
  1. #include <iostream>
  2. #include <utility>
  3.  
  4. struct Node
  5. {
  6. 	int data;
  7. 	Node *next;
  8. };
  9.  
  10. class LinkedList
  11. {
  12. private:
  13. 	Node *first;
  14. 	Node *last;
  15. public:
  16. 	LinkedList();
  17. 	LinkedList(const LinkedList &src);
  18. 	LinkedList(int A[], int num);
  19. 	~LinkedList();
  20.  
  21. 	LinkedList& operator=(const LinkedList &rhs);
  22.  
  23. 	void Display() const;
  24. 	void Merge(LinkedList &b);
  25. };
  26.  
  27. // Create Linked List using default values
  28. LinkedList::LinkedList()
  29. 	: first(NULL), last(NULL)
  30. {
  31. }
  32.  
  33. // Create Linked List using Array
  34. LinkedList::LinkedList(int A[], int n)
  35. 	: first(NULL), last(NULL)
  36. {
  37. 	Node **p = &first;
  38.  
  39. 	for (int i = 0; i < n; ++i)
  40. 	{
  41. 		Node *t = new Node;
  42. 		t->data = A[i];
  43. 		t->next = NULL;
  44.  
  45. 		*p = t;
  46. 		p = &(t->next);
  47.  
  48. 		last = t;
  49. 	}
  50. }
  51.  
  52. // Create Linked List by copying another Linked List
  53. LinkedList::LinkedList(const LinkedList &src)
  54. 	: first(NULL), last(NULL)
  55. {
  56. 	Node **p = &first;
  57.  
  58. 	for (Node *tmp = src.first; tmp; tmp = tmp->next)
  59. 	{
  60. 		Node* t = new Node;
  61. 		t->data = tmp->data;
  62. 		t->next = NULL;
  63.  
  64. 		*p = t;
  65. 		p = &(t->next);
  66.  
  67. 		last = t;
  68. 	}
  69. }
  70.  
  71. // Deleting all Node in Linked List
  72. LinkedList::~LinkedList()
  73. {
  74. 	Node *p = first;
  75.  
  76. 	while (p)
  77. 	{
  78. 		Node *tmp = p;
  79. 		p = p->next;
  80. 		delete tmp;
  81. 	}
  82. }
  83.  
  84. // Update Linked List by copying another Linked List
  85. LinkedList& LinkedList::operator=(const LinkedList &rhs)
  86. {
  87. 	if (&rhs != this)
  88. 	{
  89. 		LinkedList tmp(rhs);
  90. 		std::swap(tmp.first, first);
  91. 		std::swap(tmp.last, last);
  92. 	}
  93. 	return *this;
  94. }
  95.  
  96. // Displaying Linked List
  97. void LinkedList::Display() const
  98. {
  99. 	if (first)
  100. 	{
  101. 		std::cout << first->data;
  102. 		for (Node *tmp = first->next; tmp; tmp = tmp->next)
  103. 			std::cout << " " << tmp->data;
  104. 	}
  105. 	else
  106. 	{
  107. 		std::cout << "(empty)";
  108. 	}
  109. 	std::cout << std::endl;
  110. }
  111.  
  112. // Merge two linked list
  113. void LinkedList::Merge(LinkedList& b)
  114. {
  115. 	if ((&b == this) || (!b.first))
  116. 		return;
  117.  
  118. 	if (!first)
  119. 	{
  120. 		first = b.first; b.first = NULL;
  121. 		last = b.last; b.last = NULL;
  122. 		return;
  123. 	}
  124.  
  125. 	// Store first pointer of Second Linked List
  126. 	Node *second = b.first;
  127. 	Node *third, **tmp = &third;
  128.  
  129. 	// We find first Node outside loop, smaller number, so Third pointer will store the first Node
  130. 	// Then, we can only use tmp pointer for repeating process inside While loop
  131. 	// Use while loop for repeating process until First or Second hit NULL
  132. 	do
  133. 	{
  134. 		// If first Node data is smaller than second Node data
  135. 		if (first->data < second->data)
  136. 		{
  137. 			*tmp = first;
  138. 			tmp = &(first->next);
  139. 			first = first->next;
  140. 		}
  141. 		// If first Node data is greater than second Node data
  142. 		else
  143. 		{
  144. 			*tmp = second;
  145. 			tmp = &(second->next);
  146. 			second = second->next;
  147. 		}
  148. 		*tmp = NULL;
  149. 	}
  150. 	while (first && second);
  151.  
  152. 	// Handle remaining Node that hasn't pointed by Last after while loop
  153. 	*tmp = (first) ? first : second;
  154.  
  155. 	// Change first to what Third pointing at, which is First Node
  156. 	first = third;	
  157.  
  158. 	// Change last pointer from old first linked list to new last Node, after Merge
  159. 	Node *p = first;
  160. 	while (p->next)
  161. 	{
  162. 		p = p->next;
  163. 	}	
  164. 	last = p;
  165.  
  166. 	// Destroy second linked list because every Node it's now connect with first linked list
  167. 	// This also prevent from Double free()
  168. 	b.first = b.last = NULL;
  169. }
  170.  
  171. int main()
  172. {
  173. 	int arr1[] = {4, 8, 12, 14, 15, 20, 26, 28, 30};
  174. 	int arr2[] = {2, 6, 10, 16, 18, 22, 24};
  175. 	int size1 = sizeof(arr1) / sizeof(arr1[0]);
  176. 	int size2 = sizeof(arr2) / sizeof(arr2[0]);
  177.  
  178. 	LinkedList l1(arr1, size1);
  179. 	LinkedList l2(arr2, size2);
  180. 	LinkedList l3(l1);
  181. 	LinkedList l4;
  182.  
  183. 	std::cout << "before:" << std::endl;
  184. 	std::cout << "l1: "; l1.Display();
  185. 	std::cout << "l2: "; l2.Display();
  186. 	std::cout << "l3: "; l3.Display();
  187. 	std::cout << "l4: "; l4.Display();
  188.  
  189. 	// Merge two linked list, pass l4 as reference
  190. 	l3.Merge(l2);
  191.  
  192. 	// Copy a linked list
  193. 	l4 = l3;
  194.  
  195. 	std::cout << std::endl;
  196. 	std::cout << "after:" << std::endl;
  197. 	std::cout << "l1: "; l1.Display();
  198. 	std::cout << "l2: "; l2.Display();
  199. 	std::cout << "l3: "; l3.Display();
  200. 	std::cout << "l4: "; l4.Display();
  201.  
  202. 	return 0;
  203. }
Success #stdin #stdout 0s 5492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
before:
l1: 4 8 12 14 15 20 26 28 30
l2: 2 6 10 16 18 22 24
l3: 4 8 12 14 15 20 26 28 30
l4: (empty)

after:
l1: 4 8 12 14 15 20 26 28 30
l2: (empty)
l3: 2 4 6 8 10 12 14 15 16 18 20 22 24 26 28 30
l4: 2 4 6 8 10 12 14 15 16 18 20 22 24 26 28 30
https://ideone.com/uNDPdE
language:
C++ 4.3.2 (gcc-4.3.2)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!