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.
#=======================================================================
  #=====================================================================
  # 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)
  #       }
  #=====================================================================
 
 import collections
class SinglyLinkedList( object ):

  def __init__( self ):
    self.head , self.tail = None, None

  @classmethod
  def mergeSortedLL( self, lists ):
    tracker = [None] * len( lists )
    for i in range( len( lists ) ):
      tracker[i] = lists[i].head

    result = SinglyLinkedList()

    currMin = self.getNextMin( lists, tracker )
    while None != currMin:
      result.addToTail( currMin.data )
      currMin = self.getNextMin( lists, tracker )

    return result

  @classmethod
  def getNextMin( self, lists, tracker ):
    ndx = 0
    while ndx < len( tracker ) and None == tracker[ndx]:
      ndx += 1

    if ndx >= len( tracker ) or None == tracker[ndx]:
      return None
    min_value = tracker[ndx]

    for i in range( ndx + 1, len( lists ) ):
      if None != tracker[i] and tracker[i].data < min_value.data:
        min_value = tracker[i]
        ndx = i

    if None != min_value:
      tracker[ndx] = tracker[ndx].next

    return min_value

class Node( object ):

  def __init__( self, data, next = None ):
    self.data = data
    self.next = next
import unittest
from algorithms.SinglyLinkedList import SinglyLinkedList
import random

class Test( unittest.TestCase ):
  #=====================================================================
  # Test of mergeSortedLL method, of class SinglyLinkedList.
  #=====================================================================
  def testMergeSortedLL( self ):
    all_lists = [SinglyLinkedList()] * 9
    for i in range( len( all_lists ) ):
      size = random.randrange( len( all_lists ) )
      tmp = SinglyLinkedList()
      for x in range( size ):
        tmp.addToTail( random.randrange( 25 ) )

      tmp.sort()
      all_lists[i] = tmp

    # expected
    expected = []
    for l in all_lists:
      for i in l.toArray():
        expected.append( i )

    expected.sort()

    all_listsSize = 0
    for  l in all_lists:
      all_listsSize += l.size()

    self.assertEquals( all_listsSize, len( expected ) )

    result = SinglyLinkedList.mergeSortedLL( all_lists )
    for i in range( len( expected ) ):
      self.assertEquals( expected[i], result.deleteFromHead().data )