In [189]:

    

#2-4,partition all nodes smaller than x come before all nodes greater than or equal to x.
from linked_list import LinkedList
def partition(ll,x):
    node = ll.head
    lsmall = LinkedList()
    llarge = LinkedList()
    while node:
        if node.data < x:
            lsmall.insert(node.data)
        else:
            llarge.insert(node.data)
        node = node.next
    nodes = lsmall.head
    while nodes.next is not None:
        nodes  = nodes.next
    print lsmall, nodes.data


    

In [190]:

    

ll = LinkedList()
ll.insert(2)
ll.insert(4)
ll.insert(6)
ll.insert(7)
ll.insert(1)
print ll.__str__()
print ll.head
print ll


    

    




->1->7->6->4->2
1
->1->7->6->4->2

In [181]:

    

partition(ll,6)


    

    




->2->4->1 1

In [ ]:

    




    

In [ ]: