编写一个程序exp2-6.cpp,以单链表的首结点值2为基准将该单链表分割为两部分,使所有小于2的结点排在大于或等于2的结点之前。
时间: 2024-10-15 16:16:40 浏览: 10
在C++中编写这样的程序,我们需要首先创建一个单链表节点结构,并实现链表的基本操作,如遍历、插入和查找。然后我们可以在遍历过程中找到基准值2,通过两个指针分别跟踪小于和大于等于2的节点。
下面是一个简单的`exp2-6.cpp`示例代码:
```cpp
#include <iostream>
using namespace std;
// 链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 查找第一个大于等于基准值的节点
ListNode* findSplitNode(ListNode* head, int target) {
if (head == nullptr || head->val >= target)
return head;
ListNode* current = head;
while (current->next != nullptr && current->next->val < target) {
current = current->next;
}
return current;
}
// 将链表分割成两部分
void splitList(ListNode* &head, ListNode* &splitNode) {
if (head == nullptr)
return;
splitNode = findSplitNode(head, 2);
if (splitNode == head) { // 如果没有找到大于等于2的节点,直接返回原链表
cout << "No node with value greater than or equal to 2 found." << endl;
return;
}
ListNode* smallerHead = head; // 创建新链表头,包含小于2的节点
ListNode* smallerTail = head; // 小于2的链表尾部
for (ListNode* temp = head; temp != splitNode; temp = temp->next) {
smallerTail->next = temp;
smallerTail = smallerTail->next;
}
smallerTail->next = nullptr; // 结束小于2的部分
head = splitNode->next; // 原链表去掉已分割部分,剩余大于等于2的节点
splitNode->next = nullptr; // 分割节点断开连接
}
int main() {
// 这里假设有一个已经初始化好的链表实例,你可以根据实际需求替换这个部分
ListNode* head = new ListNode(1); // 示例链表,[1 -> 0 -> -1 -> 4 -> 3]
head->next = new ListNode(0);
head->next->next = new ListNode(-1);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(3);
ListNode* splitNode = nullptr;
splitList(head, splitNode);
// 输出结果
cout << "Original list: ";
printList(head);
cout << "\nSmaller list: ";
printList(smallerHead);
return 0;
}
// 辅助函数,用于打印链表
void printList(ListNode* head) {
while (head) {
cout << head->val << " -> ";
head = head->next;
}
cout << "nullptr" << endl;
}
```
运行此程序,它会根据链表的内容找到基准值2的位置并将其分割。如果没有大于等于2的节点,则会在主函数中给出提示。
阅读全文