给定 2 个已经排序的单向链表,合并这些列表。
例子:
列表 1: 1 2 3 5 7
列表 2: 0 4 6 7 10
---> 0 1 2 3 4 5 6 7 7 10
尽管解决方案非常简单,并且使用或不使用递归(如 http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/ 参见方法 3)有几种不同的问题实现方式,
我想知道这个实现的 O big 复杂性是什么:
- 如果其中一个列表为空,则返回另一个
- 否则使用 sortedInsert 函数将第二个列表的每个节点插入到第一个列表中,该函数基本上扫描列表直到找到正确的位置。因为 2 个列表都已经排序,所以不需要每次都比较第一个列表中的节点和所有节点,我可以从最后添加的节点开始比较。
例如:继续前面的例子,如果已经添加了 4,我可以安全地从 4 开始下一个比较:
列表 1:0 1 2 3 4 5 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;
}
最佳答案
实际上这里的合并算法是O(m + n)
,而不是O(m * n)
。
既然有了最后插入节点的指针,从那开始寻找插入下一个节点的地方,总共有多少
current = current->next
sortedInsert
中的操作最多为 m + n - 1
(结果的长度减一)。插入操作(重新链接 next
指针)的次数为 n
(第二个列表的长度)。对于每个比较
current->next->data < newNode->data
下一个操作要么是插入,要么是current = current->next
,所以比较次数最多
m + 2*n - 1
假设结果列表以第一个列表中的 m_0
个元素开始,然后是第二个列表中的 n_1
个元素,然后是第二个列表中的 m_1
个元素第一个,n_2
来自第二个,...,n_r
来自第二个,最后是 m_r
来自第一个。 m_0
和 m_r
可以为 0,所有其他数字都严格为正数。
将 n_1
block 的第一个元素与 m_0
block 的每个元素和 m_1
block 的第一个元素进行比较。该 block 的所有其他元素与第二个列表中的前一个元素进行比较,m_1
block 的第一个元素 [除非 r = 1
和 m_1 = 0
,在这种情况下比较较少]。
这使得 m_0 + 1 + (n_1 - 1)*2 = m_0 + 2*n_1 - 1
比较(或更少)。
对于后面的n_k
block ,第一个元素与n_(k-1)
block 的最后一个元素进行比较,m_的所有元素(k-1)
block ,以及 m_k
block 的第一个元素 [如果存在的话]。该 block 的其他元素都与列表 2 中的前一个元素进行比较,m_k
block 的第一个元素[如果存在],使得
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;
从循环中测试。
关于algorithm - 合并两个列表的大 O 复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16495034/