#
Merge Sorted Linked Lists

#======================================================================= # 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 )