问题描述
由于2单向链表已经排序，合并列出。
例：
List1中：1 2 3 5 7
list2中：0 4 6 7 10
---> 0 1 2 3 4 5 6 7 7 10
尽管从这一事实的解决方案是相当简单和有问题的使用或不使用递归（这样的请参阅方法3），
我想知道什么会是这样实现的0大的复杂性：
- 如果该列表中的一个是空只返回其他
- 否则插入第二列表中的每个节点到第一个使用sortedInsert功能基本上扫描列表，直到正确位置被找到。由于2列出都已经排序没有必要每次都在第一列表中的所有节点的节点进行比较，我就可以开始从最后添加的节点进行比较。
例如：用previous例如，如果持续4已被添加，我可以放心地从4开始下一个比较：
List1中：0 1 2 3 4 5 7
list2中：6 7 10
现在有4个比较6，而不是用1 2 3 4 ....
如果我将一个元素对比所有的在第一个列表的元素将是O（M * N）M =＃list2中和n =＃List1的，但考虑到这种优化是什么的复杂性？
执行：
//插入排序列表的新节点
INT sortedInsert（结构ListNode **头，结构ListNode * newNode）{
INT headUpdated = 0;
结构ListNode *电流;
//该列表是空的或新的元素已添加为第一要素
如果（*头== NULL ||（*头） - ＆GT;数据＆GT; = newNode-＆GT;数据）{
newNode-＆gt;接下来= *头;
*头= newNode;
headUpdated = 1;
}
其他 {
//插入前点定位节点
目前= *头;
而（电流 - ＆gt;下面= NULL和放大器;！＆放大器;电流 - ＆GT;下一步 - ＆GT;数据＆LT; newNode-＆GT;数据）
电流=电流 - ＆gt;接着，
newNode-＆gt;接下来=电流 - ＆gt;接着，
电流 - ＆gt;接下来= newNode;
}
返回headUpdated;
}
结构ListNode * mergeLists（结构ListNode *头1，结构ListNode * HEAD2）{
如果（头1 == NULL）
返回HEAD2;
如果（HEAD2 == NULL）
返回头1;
//存储节点中的第一个列表从哪里开始的比较
结构ListNode *第一=头1;
而（HEAD2）{
结构ListNode * head2Next = head2-＆gt;接着，
的printf（添加％D开始的％D \ n个比较，head2-＆GT;的数据，第一代＆GT;数据）;
如果（sortedInsert（安培;第一，HEAD2））
头1 =第一;
第一= HEAD2;
HEAD2 = head2Next;
}
返回头1;
}
其实，合并算法，你在这里是 O（M + N） ，不是 O（M * N）。
既然你有一个指针的最后一个插入的节点，并开始寻找要插入从该下一个节点的位置上，总数
电流=电流 - ＆gt;接着
在 sortedInsert 操作至多 M + N - 1 （结果减一的长度）。插入操作数（重链接接下来指针）是 N （第二个列表的长度）。对于每个比较
电流 - ＆GT;下一步 - ＆GT;数据＆LT; newNode-＆GT;数据
的下一个操作可以是插入一个或电流=电流 - ＆gt;接着，所以比较次数为至多
M + 2 * N - 1
让我们说，在结果列表始于 m_0 从第一个列表中的元素，然后从 N_1 元素第二，那么 M_1 从第一， N_2 从第二个，...， n_r 从第二个，然后最后 m_r 从第一。 m_0 和 m_r 可能为0，其他所有的数字都是严格正的。
在 N_1 块的第一个元素是相对于 m_0 块的每个元素的第一个元素在 M_1 块。该块的所有其他元素进行比较，以他们的predecessor在第二个列表，以及 M_1 块的第一个元素[除非 R = 1 和 M_1 = 0 ，在这种情况下有较少的比较。
这使得 m_0 + 1 +（N_1 - 1）* 2 = m_0 + 2 * N_1 - 1 比较（或更少）
有关后来的 n_k 块，第一个元素是相对于 N_（K-1）块时， M_（K-1）块的所有元素，而 m_k 块的第一要素[如果存在。块的其他元件都相对于它们predecessor在列表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＆LT; = M + 2 * N - 1。
我们可以稍微用intialising改进
结构ListNode *第一=头1;
和除去
如果（！先）
第一=头1;
从回路测试。
Given 2 singly linked lists already sorted, merge the lists.
Example:
list1: 1 2 3 5 7
list2: 0 4 6 7 10
---> 0 1 2 3 4 5 6 7 7 10
Despite from the fact that the solution is quite simple and there are several different implementations of the problem with or without using recursion (like this http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/ see Method 3),
I was wondering what would be the O big complexity of this implementation:
- If one of the lists is empty just return the other
- Otherwise insert each node of the second list into the first one using the sortedInsert function which basically scan the list until the right position is found. Because the 2 lists are both already sorted there's no need to compare each time the node with all the nodes in the first list, I can start the comparison from the last added node.
ex: continuing with the previous example if 4 has been already added I can safely start the next comparison from 4:
list1: 0 1 2 3 4 5 7
list2: 6 7 10
now compare 6 with 4 instead with 1 2 3 4....
If I would compare one element with all the elements in the first list it would be O(m*n) with m=#list2 and n=#list1, but considering this "optimisation" what is the complexity?
Implementation:
// 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;
}
Actually the merge algorithm you have here is O(m + n), not O(m * n).
Since you have a pointer to the last inserted node, and start looking for the place to insert the next node from that on, the total number of
current = current->next
operations in sortedInsert is at most m + n - 1 (length of result minus one). The number of insert operations (relinking the next pointers) is n (length of the second list). For each comparison
current->next->data < newNode->data
the next operation is either an insertion or a current = current->next, so the number of comparisons is at most
m + 2*n - 1
Let us say that the resulting list starts with m_0 elements from the first list, then n_1 elements from the second, then m_1 from the first, n_2 from the second, ..., n_r from the second, then finally m_r from the first. m_0 and m_r may be 0, all other numbers are strictly positive.
The first element of the n_1 block is compared to each element of the m_0 block and the first element of the m_1 block. All other elements of that block are compared to their predecessor in the second list, and the first element of the m_1 block [unless r = 1 and m_1 = 0, in which case there are fewer comparisons].
That makes m_0 + 1 + (n_1 - 1)*2 = m_0 + 2*n_1 - 1 comparisons (or fewer).
For the later n_k blocks, the first element is compared to the last element of the n_(k-1) block, all elements of the m_(k-1) block, and the first element of the m_k block [if that exists]. The further elements of the block are all compared to their predecessor in list 2, and the first element of the m_k block [if that exists], that makes
1 + m_(k-1) + 1 + (n_k - 1)*2 = m_(k-1) + 2*n_k
comparisons (or fewer). Since all comparisons involve at least one element of the second list, the total number of comparisons is at most
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.
We can slightly improve it by intialising
struct ListNode *first = head1;
and removing the
if (!first)
first = head1;
test from the loop.
这篇关于大O的复杂性合并两个列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！