@@ -30,6 +30,17 @@ public SinglyLinkedList() { |
30 | 30 | size = 0; |
31 | 31 | } |
32 | 32 |
|
| 33 | + /** |
| 34 | + * Init SinglyLinkedList with specified head node and size |
| 35 | + * |
| 36 | + * @param head the head node of list |
| 37 | + * @param size the size of list |
| 38 | + */ |
| 39 | + public SinglyLinkedList(Node head, int size) { |
| 40 | + this.head = head; |
| 41 | + this.size = size; |
| 42 | + } |
| 43 | + |
33 | 44 | /** |
34 | 45 | * This method inserts an element at the head |
35 | 46 | * |
@@ -66,6 +77,23 @@ public void insertNth(int data, int position) { |
66 | 77 | size++; |
67 | 78 | } |
68 | 79 |
|
| 80 | + /** |
| 81 | + * Insert element to list, always sorted |
| 82 | + * |
| 83 | + * @param data to be inserted |
| 84 | + */ |
| 85 | + public void insertSorted(int data) { |
| 86 | + Node cur = head; |
| 87 | + while (cur.next != null && data > cur.next.value) { |
| 88 | + cur = cur.next; |
| 89 | + } |
| 90 | + |
| 91 | + Node newNode = new Node(data); |
| 92 | + newNode.next = cur.next; |
| 93 | + cur.next = newNode; |
| 94 | + size++; |
| 95 | + } |
| 96 | + |
69 | 97 | /** |
70 | 98 | * This method deletes an element at the head |
71 | 99 | * |
@@ -142,7 +170,7 @@ public boolean isEmpty() { |
142 | 170 | /** |
143 | 171 | * Returns the size of the linked list |
144 | 172 | */ |
145 | | - public int getSize() { |
| 173 | + public int size() { |
146 | 174 | return size; |
147 | 175 | } |
148 | 176 |
|
@@ -160,38 +188,78 @@ public String toString() { |
160 | 188 | return builder.replace(builder.length() - 2, builder.length(), "").toString(); |
161 | 189 | } |
162 | 190 |
|
| 191 | + /** |
| 192 | + * Merge two sorted SingleLinkedList |
| 193 | + * |
| 194 | + * @param listA the first sorted list |
| 195 | + * @param listB the second sored list |
| 196 | + * @return merged sorted list |
| 197 | + */ |
| 198 | + public static SinglyLinkedList merge(SinglyLinkedList listA, SinglyLinkedList listB) { |
| 199 | + Node headA = listA.head.next; |
| 200 | + Node headB = listB.head.next; |
| 201 | + |
| 202 | + int size = listA.size() + listB.size(); |
| 203 | + |
| 204 | + Node head = new Node(); |
| 205 | + Node tail = head; |
| 206 | + while (headA != null && headB != null) { |
| 207 | + if (headA.value <= headB.value) { |
| 208 | + tail.next = headA; |
| 209 | + headA = headA.next; |
| 210 | + } else { |
| 211 | + tail.next = headB; |
| 212 | + headB = headB.next; |
| 213 | + } |
| 214 | + tail = tail.next; |
| 215 | + } |
| 216 | + if (headA == null) { |
| 217 | + tail.next = headB; |
| 218 | + } |
| 219 | + if (headB == null) { |
| 220 | + tail.next = headA; |
| 221 | + } |
| 222 | + return new SinglyLinkedList(head, size); |
| 223 | + } |
| 224 | + |
163 | 225 | /** |
164 | 226 | * Main method |
165 | 227 | * |
166 | 228 | * @param args Command line arguments |
167 | 229 | */ |
168 | 230 | public static void main(String args[]) { |
169 | 231 | SinglyLinkedList myList = new SinglyLinkedList(); |
170 | | - |
171 | 232 | assert myList.isEmpty(); |
| 233 | + assert myList.toString().equals(""); |
172 | 234 |
|
173 | 235 | myList.insertHead(5); |
174 | 236 | myList.insertHead(7); |
175 | 237 | myList.insertHead(10); |
176 | | - |
177 | | - System.out.println(myList);; // 10 -> 7 -> 5 |
| 238 | + assert myList.toString().equals("10->7->5"); |
178 | 239 |
|
179 | 240 | myList.deleteHead(); |
180 | | - |
181 | | - System.out.println(myList);; // 7 -> 5 |
| 241 | + assert myList.toString().equals("7->5"); |
182 | 242 |
|
183 | 243 | myList.insertNth(11, 2); |
184 | | - |
185 | | - System.out.println(myList);; // 7 -> 5 -> 11 |
| 244 | + assert myList.toString().equals("7->5->11"); |
186 | 245 |
|
187 | 246 | myList.deleteNth(1); |
188 | | - |
189 | | - System.out.println(myList);; // 7-> 11 |
| 247 | + assert myList.toString().equals("7->11"); |
190 | 248 |
|
191 | 249 | myList.clear(); |
192 | 250 | assert myList.isEmpty(); |
193 | 251 |
|
194 | | - System.out.println(myList); // "" |
| 252 | + /* Test MergeTwoSortedLinkedList */ |
| 253 | + SinglyLinkedList listA = new SinglyLinkedList(); |
| 254 | + SinglyLinkedList listB = new SinglyLinkedList(); |
| 255 | + |
| 256 | + for (int i = 10; i >= 2; i -= 2) { |
| 257 | + listA.insertSorted(i); |
| 258 | + listB.insertSorted(i - 1); |
| 259 | + } |
| 260 | + assert listA.toString().equals("2->4->6->8->10"); |
| 261 | + assert listB.toString().equals("1->3->5->7->9"); |
| 262 | + assert SinglyLinkedList.merge(listA, listB).toString().equals("1->2->3->4->5->6->7->8->9->10"); |
195 | 263 |
|
196 | 264 | } |
197 | 265 | } |
@@ -212,13 +280,21 @@ class Node { |
212 | 280 | */ |
213 | 281 | Node next; |
214 | 282 |
|
| 283 | + Node() { |
| 284 | + |
| 285 | + } |
| 286 | + |
215 | 287 | /** |
216 | 288 | * Constructor |
217 | 289 | * |
218 | 290 | * @param value Value to be put in the node |
219 | 291 | */ |
220 | 292 | Node(int value) { |
| 293 | + this(value, null); |
| 294 | + } |
| 295 | + |
| 296 | + Node(int value, Node next) { |
221 | 297 | this.value = value; |
222 | | - this.next = null; |
| 298 | + this.next = next; |
223 | 299 | } |
224 | 300 | } |