cc 2.4

partition.py

#2.4    prtition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.
#creat two list, <x & >= x, merge them at last


from LinkedList import LinkedList, Node

def partition(self, x):
    if self is None:
        return
    small = LinkedList()
    large = LinkedList()
    '''create two list'''
    tmp = self.head
    while tmp.next is not None:
        if tmp.data < x:
            small.AddNode(tmp.data)
        else:
            large.AddNode(tmp.data)
        tmp = tmp.next
    if self.end.data < x:
        small.AddNode(self.end.data)
    else:
        large.AddNode(self.end.data)

    small.end.next = large.head
    print 'list partition with', x
    small.printList()
#    print 'large'
#    large.printList()

'''test'''        
test = LinkedList()
test.AddNode(3)
test.AddNode(16)
test.AddNode(25)
test.AddNode(8)
test.AddNode(15)
test.AddNode(20)
print 'the original list:'
test.printList()
partition(test, 16)