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