编写一个程序exp2-7.cpp,以单链表的首结点值x为基准讲该单链表分割为两部分,使所有小于x的结点排在大于或等于x的结点之前
时间: 2023-10-26 22:20:42 浏览: 95
```c++
#include <iostream>
using namespace std;
struct Node {
int val;
Node* next;
Node(int v): val(v), next(nullptr) {}
};
void insert(Node*& head, int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
} else {
Node* cur = head;
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = newNode;
}
}
void printList(Node* head) {
Node* cur = head;
while (cur != nullptr) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
void partition(Node*& head, int x) {
Node* smallHead = nullptr, *smallTail = nullptr;
Node* bigHead = nullptr, *bigTail = nullptr;
Node* cur = head;
while (cur != nullptr) {
if (cur->val < x) {
if (smallHead == nullptr) {
smallHead = smallTail = cur;
} else {
smallTail->next = cur;
smallTail = cur;
}
} else {
if (bigHead == nullptr) {
bigHead = bigTail = cur;
} else {
bigTail->next = cur;
bigTail = cur;
}
}
cur = cur->next;
}
if (smallTail != nullptr) {
smallTail->next = bigHead;
head = smallHead;
} else {
head = bigHead;
}
if (bigTail != nullptr) {
bigTail->next = nullptr;
}
}
int main() {
Node* head = nullptr;
insert(head, 3);
insert(head, 1);
insert(head, 5);
insert(head, 2);
insert(head, 4);
cout << "Original list: ";
printList(head);
partition(head, 3);
cout << "After partition: ";
printList(head);
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)