终端定义两个链表的长度,分别输入数据,并存储至链表中(默认两个链表为非递减顺序输入)。!实现三个功能:1.将两个有序链表合并成一个新的有序链表1.两个链表允许重复数据;2.要求合并后的有序链表无重复数据;3.要求合并后的链表为非递增的有序链表
时间: 2024-10-16 21:10:00 浏览: 36
为了实现这个功能,我们可以创建两个链表结构,每个节点包含一个数据字段和一个指向下一个节点的指针。首先,我们需要定义链表节点:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
```
接下来,我们可以编写一个程序来接收用户输入,将数据存入链表,然后合并两个链表满足条件:
1. **初始化链表**:从终端接收用户输入,每输入一个整数,就创建一个新的ListNode节点并将其添加到相应的链表(`list1` 和 `list2`)的末尾,保持链表非递减顺序。
```cpp
void inputAndBuildLists(ListNode*& list1, ListNode*& list2) {
int num;
std::cout << "请输入第一个链表的数据(按空格分隔),结束输入请输入-1:" << std::endl;
while (std::cin >> num, num != -1) {
list1 = insertToSortedList(num, list1);
}
std::cout << "请输入第二个链表的数据(按空格分隔),结束输入请输入-1:" << std::endl;
while (std::cin >> num, num != -1) {
list2 = insertToSortedList(num, list2);
}
}
ListNode* insertToSortedList(int val, ListNode* &list) {
ListNode* new_node = new ListNode(val);
if (!list || list->val >= new_node->val) {
new_node->next = list;
list = new_node;
} else {
ListNode* current = list;
while (current->next && current->next->val < new_node->val) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
return list;
}
```
2. **合并两个链表**:创建一个新链表`merged_list`,遍历两个链表,依次将较小的节点添加到`merged_list`,同时检查是否已有相同的值避免重复。最后,确保`merged_list`保持非递增顺序。
```cpp
ListNode* mergeAndRemoveDuplicates(ListNode* list1, ListNode* list2) {
ListNode* merged_list = nullptr;
ListNode* tail = nullptr;
while (list1 && list2) {
if (list1->val <= list2->val) {
if (!merged_list || merged_list->val > list1->val) {
merged_list = new ListNode(list1->val);
tail = merged_list;
}
list1 = list1->next;
} else {
if (!merged_list || merged_list->val > list2->val) {
merged_list = new ListNode(list2->val);
tail = merged_list;
}
list2 = list2->next;
}
}
// 将剩余的链表连接到合并链表
if (list1) {
tail->next = list1;
} else {
tail->next = list2;
}
// 再次遍历删除重复项
while (merged_list && merged_list->next) {
if (merged_list->next->val == merged_list->val) {
ListNode* temp = merged_list->next;
merged_list->next = merged_list->next->next;
delete temp;
} else {
merged_list = merged_list->next;
}
}
return merged_list;
}
```
3. **展示合并后的链表**:打印合并后的链表。
```cpp
void printList(ListNode* list) {
ListNode* curr = list;
while (curr) {
std::cout << curr->val << " -> ";
curr = curr->next;
}
std::cout << "nullptr\n";
}
int main() {
ListNode* list1, *list2, *merged_list;
inputAndBuildLists(list1, list2);
merged_list = mergeAndRemoveDuplicates(list1, list2);
printList(merged_list);
return 0;
}
```
在这个程序中,三个功能都已经实现了:合并两个有序链表、去除重复数据以及确保合并后的链表为非递增顺序。
阅读全文