Merge Sorted Linked Lists
by Isai Damier, Android Engineer @ Google

/***************************************************************************
 * 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);
    }
  }
}