本题要求实现一个函数MergeList_L(),可合并2个有序单链表。
时间: 2024-09-20 13:15:07 浏览: 35
题目描述的是设计一个函数`MergeList_L()`,用于合并两个已排序的单链表。这个函数通常会采用迭代或递归的方式来完成,基本思路是创建一个新的头节点,然后依次比较两个链表当前节点的值,将较小的节点值添加到新链表,并移动相应的指针。当其中一个链表遍历完后,将另一个链表剩余部分直接添加到新链表的末尾。
以下是合并过程的一个简单伪代码示例:
```cpp
// 假设链表节点结构为 Node:
struct Node {
int data;
Node* next;
};
Node* MergeList_L(Node* list1, Node* list2) {
// 创建一个空链表作为结果
Node* result = nullptr;
Node* current = nullptr;
// 当两个链表都不为空时
while (list1 != nullptr && list2 != nullptr) {
// 如果list1的节点值小于list2,将其添加到结果并更新指针
if (list1->data < list2->data) {
if (result == nullptr) {
result = list1;
current = result;
} else {
current->next = list1;
current = current->next;
}
list1 = list1->next;
} else { // 否则,list2的节点值较小
if (result == nullptr) {
result = list2;
current = result;
} else {
current->next = list2;
current = current->next;
}
list2 = list2->next;
}
}
// 将未遍历完的链表余部连接到结果链表末尾
if (list1 != nullptr) {
current->next = list1;
} else {
current->next = list2;
}
return result; // 返回合并后的链表头节点
}
```
阅读全文