# use two dummy nodes to store the nodes which are smaller than the key value
# and the larger nodes
# concatenate the two linked lists by removing the dummy nodes
# O(n) in time, O(1) in space
def solution(ll, key):
    dummyNode1 = Node()
    dummyNode2 = Node()
    p1 = dummyNode1
    p2 = dummyNode2
    currNode = ll
    while currNode != None:
        if currNode.value < key:
            p1.next = currNode
            p1 = p1.next
            currNode = currNode.next
        else:
            p2.next = currNode
            p2 = p2.next
            currNode = currNode.next
    p1.next = dummyNode2.next
    return dummyNode1.next