输入一个正整数 n(0<n<=9)和一组(n个)升序的整数,建立单向链表,再输入一个整数 x,把 x 插入到这组数据中,使该组数据仍然有序。
时间: 2024-05-04 22:19:15 浏览: 92
这道题可以按照以下步骤来实现:
1. 定义链表节点结构体,包含一个整数值和一个指向下一个节点的指针。
2. 读入 n 和 n 个升序的整数,依次创建链表节点,并将它们连接成链表。
3. 读入要插入的整数 x,在链表中找到插入位置,将 x 插入链表中。
4. 输出链表中的所有元素。
下面是完整的 C++ 代码实现:
```cpp
#include<iostream>
using namespace std;
// 链表节点结构体
struct ListNode {
int val; // 节点的值
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 构造函数
};
// 在链表中插入一个值为 x 的节点,使链表仍然有序
ListNode* insert(ListNode* head, int x) {
ListNode* node = new ListNode(x); // 创建新节点
if (head == NULL || x < head->val) { // x 比头节点小,插入在链表头部
node->next = head;
return node;
}
ListNode* cur = head;
while (cur->next != NULL && cur->next->val < x) { // 找到插入位置
cur = cur->next;
}
node->next = cur->next; // 插入新节点
cur->next = node;
return head;
}
int main() {
int n;
cin >> n;
ListNode* head = NULL;
for (int i = 0; i < n; i++) { // 创建链表
int x;
cin >> x;
head = insert(head, x);
}
int x;
cin >> x;
head = insert(head, x); // 插入新节点
ListNode* cur = head;
while (cur != NULL) { // 输出链表
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
return 0;
}
```
输入样例:
```
3
1 3 5
4
```
输出样例:
```
1 3 4 5
```
阅读全文