大O复杂度合并两个列表

Question

给定已排序的两个单链表，合并这些列表。

示例：
list1: 1 2 3 5 7
list2: 0 4 6 7 10
---

尽管这个解决方案非常简单，并且有几个不同的问题实现，不管是否使用递归（如下所示http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/见方法3），

我想知道这个实现有多复杂：

1. 如果其中一个列表是空的，只需返回另一个
2. 否则将第二个列表的每个节点插入到第一个列表中，使用sorted插入函数，该函数基本上扫描列表，直到找到正确的位置。因为这两个列表都已经排序了，所以不需要每次将节点与第一个列表中的所有节点进行比较，我可以从最后一个添加的节点开始比较。

例：继续上一个示例如果已经添加了4，我可以安全地从4开始下一次比较：
列表1:0 1 2 345 7
列表2:6 7 10
现在将6与4进行比较，而不是与1 2 3 4进行比较。。。。

如果我将一个元素与第一个列表中的所有元素进行比较，它将是O（m*n），m=#list2和n=#list1，但是考虑到这种“优化”，复杂性是什么？

实施：

// 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;
}

Answer 1

实际上，这里的合并算法是O（mn），而不是O（mn）。

由于您有一个指向上一个插入节点的指针，并从该指针开始查找插入下一个节点的位置，因此

current = current->next

sortedInrett中的操作至多为m n-1（结果长度减1）。插入操作（重新链接下一个指针）的数量为n（第二个列表的长度）。对于每个比较

current->next->data < newNode->data

下一个操作要么是插入，要么是当前=当前-

m + 2*n - 1

假设结果列表从第一个列表的m_0元素开始，然后从第二个列表的n_1元素开始，然后从第一个列表的m_1开始，从第二个列表的n_2开始n\u r从第二个开始，然后最后从第一个开始m\u rm_0和m_r可能为0，所有其他数字都严格为正。

将n_1块的第一个元素与m_0块的每个元素以及m_1块的第一个元素进行比较。将该块的所有其他元素与第二个列表中的前一个元素以及m_1块的第一个元素进行比较[除非r=1和m_1=0，在这种情况下比较较少]。

这使得m1（n1-1）*2=m2*n1-1比较（或更少）。

对于后面的n_k块，将第一个元素与n_k（k-1）块的最后一个元素、m_k（k-1）块的所有元素以及m_k块的第一个元素（如果存在）进行比较。块的其他元素都与列表2中的前一个元素进行比较，m_k块的第一个元素[如果存在的话]，这使得

 1 + m_(k-1) + 1 + (n_k - 1)*2 = m_(k-1) + 2*n_k

比较（或更少）。由于所有比较都至少涉及第二个列表中的一个元素，因此比较的总数最多为

m_0 + 2*n_1 - 1 + m_1 + 2*n_2 + m_2 + 2*n_3 + ... + m_(r-1) + 2*n_r <= m + 2*n - 1.

我们可以稍微改进一下

    struct ListNode *first = head1;

以及移除

    if (!first)
        first = head1;

从循环中进行测试。