Python3 solution - create two lists and merge


#1
class Solution:
    # @param A : head node of linked list
    # @param B : integer
    # @return the head node in the linked list
    def partition(self, A, B):
        #first  and second are two list having nodes of values <B and >=B. t1 is head of first list
        first, second, t1 = None, None, None
        head = A
        while head is not None:
            if head.val < B:
                if first is None:
                    first = head
                    t1 = first
                else:
                    first.next =  head
                    first = first.next
            else:
                if second is None:
                    second = head
                    # t2 is head of second list
                    t2 = second
                else:
                    second.next = head
                    second = second.next
            head = head.next
        second.next = None
        # check if there are no elements less than B
        if t1 is not None:
            first.next = t2
            return t1
        else:
            return t2