用C++,设有两条有序链表(即 data 域元素的关键字由前往后不断增大),试设计算法,将这两 条链表合并为一条新的有序链表,原链表不变。两条链表中 data 域关键字相同的元素只选 取一个存储到新的有序链表中,不同的元素都存储到新的有序链表中。 要求: ➢ 直接编写链表的友元函数完成该功能。 ➢ 链表的 data 域可存储用户自定义类对象。 ➢ 编写测试 main()函数测试线性表的正确性
时间: 2023-05-29 12:06:05 浏览: 32
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T data;
Node<T>* next;
Node<T>(T d) : data(d), next(nullptr) {}
};
template <class T>
class LinkedList {
public:
LinkedList<T>() : head(nullptr) {}
void insert(T data) {
Node<T>* newNode = new Node<T>(data);
if (!head) {
head = newNode;
} else {
Node<T>* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
}
}
friend LinkedList<T> merge(LinkedList<T>& list1, LinkedList<T>& list2) {
LinkedList<T> newList;
Node<T>* current1 = list1.head;
Node<T>* current2 = list2.head;
while (current1 && current2) {
if (current1->data < current2->data) {
newList.insert(current1->data);
current1 = current1->next;
} else if (current1->data > current2->data) {
newList.insert(current2->data);
current2 = current2->next;
} else {
newList.insert(current1->data);
current1 = current1->next;
current2 = current2->next;
}
}
while (current1) {
newList.insert(current1->data);
current1 = current1->next;
}
while (current2) {
newList.insert(current2->data);
current2 = current2->next;
}
return newList;
}
void display() {
Node<T>* current = head;
while (current) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
private:
Node<T>* head;
};
int main() {
LinkedList<int> list1;
list1.insert(1);
list1.insert(3);
list1.insert(5);
LinkedList<int> list2;
list2.insert(2);
list2.insert(4);
list2.insert(6);
LinkedList<int> newList = merge(list1, list2);
newList.display();
return 0;
}