用c++写1、利用头插法或尾插法建立单链表。 2、对已建立的单链表实现插入、删除等基本操作。 3、输出链表所有结点数据。 4、编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并计算表长。 5、要求利用原来两个单链表的结点存放归并后的单链表。
时间: 2024-09-24 09:15:53 浏览: 78
1. 在C++中,我们可以使用头插法(也称为前向追加)或尾插法(也称为后向追加)来构建单链表。以下是头插法的简单示例:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
void insertHead(ListNode*& head, int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
head = newNode;
}
```
尾插法则稍有不同,通常会有一个专门的`tail`指针指向最后一个节点:
```cpp
ListNode* tail = nullptr; // 初始化 tail 为空
void insertTail(ListNode*& tail, int val) {
ListNode* newNode = new ListNode(val);
if (tail == nullptr) {
head = newNode;
} else {
tail->next = newNode;
}
tail = newNode; // 更新 tail 指向新节点
}
```
2. 对单链表进行插入和删除操作:
- 插入:如上所述,针对头尾分别有不同的函数。
- 删除:例如删除给定值的第一个节点:
```cpp
void removeElement(ListNode*& head, int target) {
if (head == nullptr || head->val == target) {
ListNode* temp = head;
head = head->next;
delete temp;
return;
}
ListNode* current = head;
while (current->next != nullptr && current->next->val != target) {
current = current->next;
}
if (current->next != nullptr) {
ListNode* toDelete = current->next;
current->next = current->next->next;
delete toDelete;
}
}
```
3. 输出链表所有节点的数据:
```cpp
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
std::cout << current->val << " ";
current = current->next;
}
std::cout << std::endl;
}
```
4. 归并两个单链表并排序:
这个过程需要比较两个链表的节点,然后选择较小的一个添加到结果链表,并更新指针。这可以是一个递归或迭代的过程。这里仅提供一个简化的示例,假设已经实现了比较函数`compareVal`:
```cpp
ListNode* mergeSortedLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr) return list2;
if (list2 == nullptr) return list1;
if (compareVal(list1->val, list2->val) < 0) {
list1->next = mergeSortedLists(list1->next, list2);
return list1;
} else {
list2->next = mergeSortedLists(list1, list2->next);
return list2;
}
}
```
5. 要求利用原来的链表节点存储合并后的链表,你可以将新的节点创建在原节点结构中,比如创建一个新的`ListNode`对象并将它链接到原有的链表节点,而不是创建全新的链表。
阅读全文