from linked_list import LinkedList
from linked_list_node import LinkedListNode
from print_list import print_list_with_forward_arrow

def merge_two_lists(head1, head2):  
    # Create a placeholder node to mark the start of merged list
    dummy = LinkedListNode(-1)

    # Initialize a pointer to keep track of the current position
    prev = dummy  

    # Iterate while both linked lists have remaining nodes
    while head1 and head2:
        if head1.data <= head2.data:

            # Connect the current node of list1 to the merged list
            prev.next = head1

            # Move to the next node in list1
            head1 = head1.next
        else:
            # Connect the current node of list2 to the merged list
            prev.next = head2

            # Move to the next node in list2
            head2 = head2.next

        # Move the pointer to the end of the merged list
        prev = prev.next

    # Connect any remaining nodes of list1 or list2 to the merged list
    if head1:
        prev.next = head1
    else:
        prev.next = head2

    # Return the merged linked list starting from the node after prehead
    return dummy.next

# Driver code
def main():
    input = (
        [[1, 2, 3],[1, 2, 3]],
        [[25, 33, 99], [1]],
        [[], [1]],
        [[-77, 0, 5], [1, 2, 7]],
        [[], []],
    )

    for i in range(len(input)):
        list1 = LinkedList()
        list2 = LinkedList()
        list1.create_linked_list(input[i][0])
        list2.create_linked_list(input[i][1])
        
        print(i+1, ".\tInput: ")
        print("\t", end = " ") 
        print_list_with_forward_arrow(list1.head)
        print("\n\t", end = " ") 
        print_list_with_forward_arrow(list2.head)
        print("\n\n\tOutput: ")
        print("\t", end = " ") 
        
        merged = merge_two_lists(list1.head, list2.head)
        print_list_with_forward_arrow(merged)
        print("\n", "-"*100)

if __name__ == "__main__":
    main()