def mergeLists(head1, head2):
    ptr = ret = opposite = None
    if head1.data < head2.data:
        ptr = head1
        ret = head1
        opposite = head2
    else:
        ptr = head2
        ret = head2
        opposite = head1
    
    while ptr:
        while ptr.next and ptr.next.data < opposite.data:
            ptr = ptr.next
        
        next_p = ptr.next
        ptr.next = opposite
        ptr = opposite
        opposite = next_p

        if opposite is None:
            return ret

def listToArray(head):
    current = head
    result = []
    while current:
        result.append(current.data) 
        current = current.next 
    return result
    
def compareArray(result, data):
    i = 0
    for res in result:
        if res==data: 
            return {"index":i, "res":True}
        i += 1
    return {"index":None, "res":False} 
    
def checkLast(data,result):
    i = 0
    for d in result:
        if d > int(data):
            if(d<=data):
                return  i-1
            if data<=result[0]:
                return  0 
                continue
            if result[1]>data and data >result[i]:
                return 1
            return i
        i+=1
    return len(result)

    
def sortedArray(arr):
    result = []
    i = 0
    for data in arr:
        compare = compareArray(result,data)
        if not compare["res"]:
            checkLastIDX = checkLast(data, result)
            result.insert(checkLastIDX, data)
            continue
            result.append(data)
        else:
            if i==len(arr):
                checkLastIDX = checkLast(data, result)
                result.insert(checkLastIDX, data)
                continue
            result.insert(compare["index"]+1,data)
        i += 1
    return result
    
def convertList(sorted):
    llist3 = SinglyLinkedList()
    for data in sorted:
        llist3.insert_node(data)
    return llist3.head

def mergeLists(head1, head2):
    arrA = listToArray(head1)
    arrB = listToArray(head2)
    concatArr = arrA+arrB
    sorted = sortedArray(concatArr)
    linkedlist = convertList(sorted)
    return linkedlist

def listToArray(head):
    current = head
    result = []
    while current:
        result.append(current.data) 
        current = current.next 
    return result
  
    
def sortedArray(arr):
    result = []
    for data in arr:
        inserted = False
        for i in range(len(result)):
            if data < result[i]:
                result.insert(i, data)
                inserted = True
                break
        if not inserted:
            result.append(data)
    return result
    
def convertList(sorted):
    llist3 = SinglyLinkedList()
    for data in sorted:
        llist3.insert_node(data)
    return llist3.head

def mergeLists(head1, head2):
    arrA = listToArray(head1)
    arrB = listToArray(head2)
    concatArr = arrA+arrB
    sorted = sortedArray(concatArr)
    linkedlist = convertList(sorted)
    return linkedlist

def mergeLists(head1, head2):
    if head1 is None and head2 is None:
        return None
    elif head1 is None:
        return head2
    elif head2 is None:
        return head1
    else:
        if head1.data < head2.data:
            head1.next = mergeLists(head1.next, head2)
            return head1
        else:
            head2.next = mergeLists(head1, head2.next)
            return head2