Big O Komplexität zum Zusammenführen von zwei Listen

2 einfach verknüpfte Listen bereits sortiert sind, Zusammenführen der Listen.

Beispiel:

Liste1: 1 2 3 5 7

liste2: 0 4 6 7 10

---> 0 1 2 3 4 5 6 7 7 10

Trotz der Tatsache, dass die Lösung ist ganz einfach und es gibt verschiedene Implementierungen des Problems mit oder ohne Verwendung von Rekursion (wie dieser http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/ siehe Methode 3),

Ich Frage mich, was wäre der O große Komplexität dieser Umsetzung:

1. Wenn eine der Listen leer ist, nur zurück, die anderen
2. Sonst einfügen der einzelnen Knoten der zweiten Liste in die erste, mit der sortedInsert Funktion, die im Grunde Scannen Sie die Liste, bis Sie die richtige position gefunden ist. Da die 2 Listen schon sortiert, es gibt keine Notwendigkeit zu vergleichen, die jedes mal, wenn der Knoten mit allen Knoten, die in der ersten Liste kann ich starten Sie den Vergleich aus den zuletzt hinzugefügten Knoten.

ex: weiter mit dem vorherigen Beispiel, wenn Sie 4 wurde bereits Hinzugefügt wurden, kann ich sicher anfangen, den nächsten Vergleich aus 4:

Liste1: 0 1 2 3 4 5 7

liste2: 6 7 10

vergleichen Sie jetzt 6 mit 4 statt mit 1 2 3 4....

Wenn ich vergleichen würde ein element mit allen Elementen in der ersten Liste wäre es O(m*n) mit m=#list2 und n=#Liste1, aber in Anbetracht dieser "Optimierung" was ist die Komplexität?

Umsetzung:

//Insert a new node in a sorted list
int sortedInsert(struct ListNode **head, struct ListNode* newNode) {
    int headUpdated = 0;
    struct ListNode *current;

    //The list is empty or the new element has to be added as first element
    if (*head == NULL || (*head)->data >= newNode->data) {
        newNode->next = *head;
        *head = newNode;
        headUpdated = 1;
    }
    else {
        //Locate the node before the point of insertion
        current = *head;
        while (current->next != NULL && current->next->data < newNode->data)
            current = current->next;

        newNode->next = current->next;
        current->next = newNode;
    }

    return headUpdated;
}


struct ListNode *mergeLists(struct ListNode *head1, struct ListNode *head2) {
    if (head1 == NULL)
        return head2;

    if (head2 == NULL)
        return head1;

    //Store the node in the first list where to start the comparisons
    struct ListNode *first = head1;

    while (head2) {
        struct ListNode *head2Next = head2->next;

        printf("Adding %d starting comparison from %d\n", head2->data, first->data);
        if (sortedInsert(&first, head2))
            head1 = first;

        first = head2;
        head2 = head2Next;
    }

    return head1;
}