编写一个 SortedMerge() 函数，该函数接受两个列表，每个列表都按升序排序，然后将这两个列表合并为一个按升序排列的列表。SortedMerge() 应该返回新列表。应该通过将前两个列表的节点拼接在一起来制作新列表。
例如如果第一个链表 a 是 5->10->15 而另一个链表 b 是 2->3->20，那么 SortedMerge() 应该返回一个指向合并链表 2-> 头节点的指针3->5->10->15->20。
有很多情况需要处理：a或b可能为空，在处理过程中a或b可能先用完，最后出现结果列表开始为空，构建的问题它在经历'a'和'b'时向上。
方法一（使用虚拟节点）
这里的策略使用临时虚拟节点作为结果列表的开始。指针 Tail 始终指向结果列表中的最后一个节点，因此添加新节点很容易。
当结果列表为空时，虚拟节点为尾部提供初始指向的对象。这个虚拟节点是有效的，因为它只是临时的，并且在堆栈中分配。循环继续，从“a”或“b”中删除一个节点，并将其添加到尾部。什么时候我们完成了，结果在 dummy.next 中。
下面是上述方法的实现：
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; Node* SortedMerge(Node* a, Node* b) { Node dummy; Node* tail = &dummy; dummy.next = NULL; while (1) { if (a == NULL) { tail->next = b; break; } else if (b == NULL) { tail->next = a; break; } if (a->data <= b->data) MoveNode(&(tail->next), &a); else MoveNode(&(tail->next), &b); tail = tail->next; } return(dummy.next); } void MoveNode(Node** destRef, Node** sourceRef) { Node* newNode = *sourceRef; assert(newNode != NULL); *sourceRef = newNode->next; newNode->next = *destRef; *destRef = newNode; } void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node *node) { while (node!=NULL) { cout<<node->data<<" "; node = node->next; } } int main() { Node* res = NULL; Node* a = NULL; Node* b = NULL; push(&a, 15); push(&a, 10); push(&a, 5); push(&b, 20); push(&b, 3); push(&b, 2); res = SortedMerge(a, b); cout << "Merged Linked List is: \n"; printList(res); return 0; }
输出 ：
Merged Linked List is: 2 3 5 10 15 20
方法 2（使用本地引用）
该解决方案在结构上与上述非常相似，但它避免使用虚拟节点。相反，它维护一个 struct node** 指针 lastPtrRef，该指针始终指向结果列表的最后一个指针。这解决了与虚拟节点相同的情况——在结果列表为空时处理它。如果您试图在其尾部构建一个列表，则可以使用虚拟节点或结构节点**“引用”策略（有关详细信息，请参阅第 1 节）。
Node* SortedMerge(Node* a, Node* b) { Node* result = NULL; Node** lastPtrRef = &result; while(1) { if (a == NULL) { *lastPtrRef = b; break; } else if (b==NULL) { *lastPtrRef = a; break; } if(a->data <= b->data) { MoveNode(lastPtrRef, &a); } else { MoveNode(lastPtrRef, &b); } lastPtrRef = &((*lastPtrRef)->next); } return(result); }
方法 3（使用递归）
合并是那些很好的递归问题之一，其中递归解决方案代码比迭代代码清晰得多。但是，您可能不想将递归版本用于生产代码，因为它将使用与列表长度成正比的堆栈空间。
Node* SortedMerge(Node* a, Node* b) { Node* result = NULL; if (a == NULL) return(b); else if (b == NULL) return(a); if (a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return(result); }
时间复杂度： 因为我们完全遍历了两个列表。因此，时间复杂度为O(m+n) ，其中 m 和 n 是要合并的两个列表的长度。
方法 4（反转列表）
这个想法包括首先反转给定的列表，反转后，遍历两个列表直到最后，然后比较两个列表的节点，并在结果列表的开头插入具有较大值的节点。通过这种方式，我们将按递增顺序获得结果列表。
1) 将结果列表初始化为空：head = NULL。 2) 令 'a' 和 'b' 分别是第一个和第二个列表的头部。 3）反转两个列表。 4) While (a != NULL and b != NULL) a) 找出两个（当前'a'和'b'）中 的较大者 b）在结果列表的前面插入节点的较大值。 c) 在较大节点列表中向前移动。 5) 如果在 'a' 之前 'b' 变为 NULL，则将 'a' 的所有节点插入 到结果列表的开头。 6) 如果在 'b' 之前 'a' 变为 NULL，则将 'b' 的所有节点插入 到结果列表的开头。
下面是上述解决方案的实现。
#include <iostream> using namespace std; struct Node { int key; struct Node* next; }; Node* reverseList(Node* head) { if (head->next == NULL) return head; Node* rest = reverseList(head->next); head->next->next = head; head->next = NULL; return rest; } Node* sortedMerge(Node* a, Node* b) { a = reverseList(a); b = reverseList(b); Node* head = NULL; Node* temp; while (a != NULL && b != NULL) { if (a->key >= b->key) { temp = a->next; a->next = head; head = a; a = temp; } else { temp = b->next; b->next = head; head = b; b = temp; } } while (a != NULL) { temp = a->next; a->next = head; head = a; a = temp; } while (b != NULL) { temp = b->next; b->next = head; head = b; b = temp; } return head; } void printList(struct Node* Node) { while (Node != NULL) { cout << Node->key << " "; Node = Node->next; } } Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->next = NULL; return temp; } int main() { struct Node* res = NULL; Node* a = newNode(5); a->next = newNode(10); a->next->next = newNode(15); a->next->next->next = newNode(40); Node* b = newNode(2); b->next = newNode(3); b->next->next = newNode(20); cout << "List A before merge: \n"; printList(a); cout << "\nList B before merge: \n"; printList(b); res = sortedMerge(a, b); cout << "\nMerged Linked List is: \n"; printList(res); return 0; }
输出：
List A before merge: 5 10 15 40 List B before merge: 2 3 20 Merged Linked List is: 2 3 5 10 15 20 40
时间复杂度： 因为我们完全遍历了两个列表。因此，时间复杂度为 O(m+n)，其中 m 和 n 是要合并的两个列表的长度。
