给定两个分别由 N 和 M 个节点组成的有序链表。我们的任务是将这两个列表合并（原地操作）并返回合并后列表的头节点。
示例：
> 输入： a: 5->10->15, b: 2->3->20
> 输出： 2->3->5->10->15->20
>
> 输入： a: 1->1, b: 2->4
> 输出： 1->1->2->4
核心思想是使用一个临时的虚拟节点作为结果列表的起始点。指针 Tail 始终指向结果列表中的最后一个节点，这使得追加新节点变得非常简单。请参考下面的图示以便更好地理解：
!Merge-Two-Sorted-LinkedLists1
让我们按照以下步骤来解决这个问题：
- 首先，为新的合并链表创建一个虚拟节点。
- 现在，创建两个指针，一个指向 list1，另一个指向 list2。
- 遍历这两个列表，直到其中一个耗尽为止。
- 如果任一列表中当前节点的值小于另一个指针所指的节点，就将该节点加入到我们的合并列表中，并递增该指针。
下面是上述方法的实现：
C++
// using dummy nodes
#include
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int new_data)
{
this->data = new_data;
this->next = nullptr;
}
};
// Function that takes two lists sorted in increasing order,
// and splices their nodes together to make one big sorted
// list which is returned.
Node mergeSortedList(Node first, Node* second) {
// A dummy first node to hang the result on
Node dummy(-1);
// Tail points to the last result node
Node* tail = &dummy;
// So tail->next is the place to add new nodes to the
// result
while (1) {
if (first == NULL) {
// If either list runs out, use the other list
tail->next = second;
break;
}
else if (first == NULL) {
tail->next = first;
break;
}
if (first->data data) {
// Move the front node from ‘a‘ to the result
// list
Node* newNode = first;
first = first->next;
newNode->next = tail->next;
tail->next = newNode;
}
else {
// Move the front node from ‘b‘ to the result
// list
Node* newNode = second;
second = second->next;
newNode->next = tail->next;
tail->next = newNode;
}
tail = tail->next;
}
return (dummy.next);
}
// Driver code
int main() {
// Create a hard-coded linked list:
// 2 -> 4 -> 8 -> 9
Node* first = new Node(2);
first->next = new Node(4);
first->next->next = new Node(8);
first->next->next->next = new Node(9);
// Create another hard-coded linked list:
// 1 -> 3 -> 8 -> 10
Node* second = new Node(1);
second->next = new Node(3);
second->next->next = new Node(8);
second->next->next->next = new Node(10);
Node* mergedList = mergeSortedList(first, second);
Node* temp = mergedList;
cout << "Merged Link List is:" << endl;
while (temp) {
cout <data << " ";
temp = temp->next;
}
return 0;
}
`
C
`
// C program to merge two sorted linked lists
// using dummy nodes
#include
#include
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createNode(int new_data) {
Node newNode = (Node)malloc(sizeof(Node));
newNode->data = new_data;
newNode->next = NULL;
return newNode;
}
// Function that takes two lists sorted in increasing order,
// and splices their nodes together to make one big sorted
// list which is returned.
Node mergeSortedList(Node first, Node* second) {
// A dummy first node to hang the result on
Node dummy;
dummy.data = -1;
dummy.next = NULL;
// Tail points to the last result node
Node* tail = &dummy;
// So tail->next is the place to add new nodes to the
// result
while (1) {
if (first == NULL) {
// If either list runs out, use the other list
tail->next = second;
break;
}
else if (second == NULL) {
tail->next = first;
break;
}
if (first->data data) {
// Move the front node from ‘first‘ to the
// result list
Node* newNode = first;
first = first->next;
newNode->next =