2 つの単方向リストが既にソートされている場合、リストをマージします。
例:
list1: 1 2 3 5 7
list2: 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 を参照) )、
この実装の非常に複雑な点は何だろうと思っていました:
- リストの 1 つが空の場合は、もう一方を返すだけです
- それ以外の場合は、正しい位置が見つかるまで基本的にリストをスキャンする sortedInsert 関数を使用して、2 番目のリストの各ノードを最初のリストに挿入します。2 つのリストは両方とも既に並べ替えられているため、ノードを最初のリストのすべてのノードと毎回比較する必要はありません。最後に追加されたノードから比較を開始できます。
例: 4 が既に追加されている場合、前の例を続行すると、4 から次の比較を安全に
開始できます
。 ..
1 つの要素を最初のリストのすべての要素と比較すると、m=#list2 および n=#list1 の O(m*n) になりますが、この「最適化」を考慮すると、複雑さは何ですか?
実装：
// 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;
}