In [238]:

    

#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
    if nodes is None:
        print llarge
    else:
        while nodes.next is not None:
            nodes = nodes.next
        nodes.next = llarge.head
        print lsmall


    

In [239]:

    

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 [240]:

    

partition(ll,7)


    

    




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

In [ ]: