/***************************************************************************
* Author: Isai Damier
* Title: Singly Linked List
* Project: geekviewpoint
* Package: datastructure
*
* Description: A LinkedList is a data structure that allows access
* to a collection of data using pointers/references. While an
* array can also be defined as above, LinkedLists and arrays differ
* in how they are stored in memory and in the operations they
* allow. Unlike an array that must be stored in a block of memory,
* the nodes of a LinkedList can be stored anywhere because each
* node has a reference to the node that succeeds it. Because the
* nodes are stored so loosely, inserting nodes into a LinkedList
* is easy; whereas in an array, all the succeeding elements must
* be shifted. Of course, insertion also means changing the size of
* the array, which means creating the entire array anew.
*
* Perhaps the greatest beauty of LinkedList is that it allows
* accessing an entire sequence of nodes using only one variable:
* a reference to the first node in the sequence.
*
* Countless operations can be performed on LinkedLists. Following
* are a few, ranging from the common to the very interesting.
**************************************************************************/
public class SinglyLinkedList {
/*****************************************************************
* Time Complexity of Solution:
* O(n).
*
* Description: Given an array of sorted link lists, merge all
* the lists and return one large sorted list.
*
* Technical Details: Personally, I think of the process for
* merging two sorted arrays and apply it to n sorted LinkedList.
* The idea is to continuously find the mininum available
* node and add it to the result LinkedList. This same technique
* can be applied to sorting very large files in external drives.
*
* If a programmer does not want the duplicates, simply replace
* result.addToTail(currMin.data);
* with
* if(result.tail.data != currMin.data){
* result.addToTail(currMin.data);
* }
*****************************************************************/
static public SinglyLinkedList mergeSortedLL(SinglyLinkedList[] lists) {
Node[] tracker = new Node[lists.length];
for (int i = 0; i < lists.length; i++) {
tracker[i] = lists[i].head;
}
SinglyLinkedList result = new SinglyLinkedList();
Node currMin = getNextMin(lists, tracker);
while (null != currMin) {
result.addToTail(currMin.data);
currMin = getNextMin(lists, tracker);
}
return result;
}
private static Node getNextMin(SinglyLinkedList[] lists, Node[] tracker) {
int ndx = 0;
while (ndx < tracker.length && null == tracker[ndx]) {
ndx++;
}
if (ndx >= tracker.length || null == tracker[ndx]) {
return null;
}
Node min = tracker[ndx];
for (int i = ndx + 1; i < lists.length; i++) {
if (null != tracker[i] && tracker[i].data < min.data) {
min = tracker[i];
ndx = i;
}
}
if (null != min) {
tracker[ndx] = tracker[ndx].next;
}
return min;
}
}
public class SinglyLinkedListTest {
/**
* Test of mergeSortedLL method, of class SinglyLinkedList.
*/
@Test
public void testMergeSortedLL() {
System.out.println("mergeSortedLL");
SinglyLinkedList[] lists = new SinglyLinkedList[9];
Random rand = new Random();
for (int i = 0; i < lists.length; i++) {
int size = rand.nextInt(lists.length);
SinglyLinkedList tmp = new SinglyLinkedList();
for (int x = 0; x < size; x++) {
tmp.addToTail(rand.nextInt(25));
}
tmp.sort();
lists[i] = tmp;
}
//expected
List<Integer> expected = new ArrayList<Integer>();
for (SinglyLinkedList l : lists) {
for (int i : l.toArray()) {
expected.add(i);
}
}
Integer[] exp = expected.toArray(new Integer[0]);
Arrays.sort(exp);
int listsSize = 0;
for (SinglyLinkedList l : lists) {
listsSize += l.size();
}
assertEquals(listsSize, exp.length);
SinglyLinkedList result = SinglyLinkedList.mergeSortedLL(lists);
for (int i = 0; i < exp.length; i++) {
assertEquals(exp[i].intValue(), result.deleteFromHead().data);
}
}
}