利用C++语言创建单向链表并完成对链表的如下操作: 1、创建一条含正整数结点的无序链表 2、链表结点的输出 3、链表结点的升序排序 4、链表结点插入 5、链表结点删除 6、链表逆序(升序变降序) 7、链表拆分,将链表拆分成由奇数和偶数结点组成的两条链表 8、释放链表
时间: 2024-08-16 09:04:22 浏览: 36
在C++中,我们可以使用结构体定义链表节点,并提供相应的函数来操作链表。以下是基本步骤:
1. **创建链表节点**:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
```
2. **创建无序链表**:
```cpp
ListNode* createList(vector<int>& nums) {
ListNode* head = nullptr;
for (int num : nums) {
head = insert(head, num);
}
return head;
}
// 插入节点函数
ListNode* insert(ListNode* head, int val) {
ListNode* newNode = new ListNode(val);
if (!head) {
head = newNode;
} else {
ListNode* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
}
return head;
}
```
3. **链表结点输出**:
```cpp
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
}
```
4. **升序排序**:
```cpp
ListNode* sortList(ListNode* head) {
// 使用归并排序等算法对链表进行排序
// 这里仅提供思路,实际代码需要实现链表比较和合并操作
}
```
5. **链表结点插入**:
已经在`createList`函数中包含插入操作。
6. **链表逆序**:
```cpp
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* nextTemp = nullptr;
while (curr) {
nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
```
7. **链表拆分**:
```cpp
void splitList(ListNode* head) {
ListNode* evenHead = nullptr, *evenTail = nullptr;
ListNode* oddHead = nullptr, *oddTail = nullptr;
ListNode* current = head;
while (current) {
if (current->val % 2 == 0) {
if (!evenHead) {
evenHead = current;
evenTail = evenHead;
} else {
evenTail->next = current;
evenTail = evenTail->next;
}
} else {
if (!oddHead) {
oddHead = current;
oddTail = oddHead;
} else {
oddTail->next = current;
oddTail = oddTail->next;
}
}
current = current->next;
}
if (evenTail) {
evenTail->next = nullptr;
}
if (oddTail) {
oddTail->next = nullptr;
}
}
```
8. **释放链表**:
```cpp
void freeList(ListNode* head) {
while (head) {
ListNode* temp = head;
head = head->next;
delete temp;
}
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)