编写一个程序exp2-6.cpp,已给定值x为基准将单链表分割为两部分, 所有小于x的结点排在大于或等于x的结点之前。C++使用简单的方法,使得Dev-C++编译器能运行
时间: 2024-11-30 17:19:26 浏览: 23
在C++中,编写一个名为exp2-6.cpp
的程序,可以使用迭代的方式遍历链表并根据给定值x分割它。这里是一个简单的示例,假设我们有一个结构体ListNode
表示链表节点:
#include <iostream>
using namespace std;
// 链表节点定义
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 辅助函数,用于比较节点值是否小于x
bool cmpNode(ListNode* node, int x) {
return node->val < x;
}
// 主函数:分割链表
void splitList(ListNode*& head, int x) {
if (head == nullptr || head->next == nullptr) {
// 如果链表为空或只有一个元素,直接返回
return;
}
ListNode* smallHead = new ListNode(0); // 创建一个新的头节点,用于存放小数部分的链表
ListNode* largeHead = head; // 初始大数部分就是原链表
// 分割过程:较小的节点连接到smallHead
while (head != nullptr && cmpNode(head, x)) {
smallHead->next = head;
smallHead = smallHead->next;
head = head->next;
}
// 小数部分结束,将剩余部分连接回原链表
smallHead->next = largeHead; // 将smallHead指向的大数部分接回原链表的头部
head = smallHead->next; // 更新原始链表头指针
}
int main() {
// 假设已经创建了一个链表实例,例如:head = {5, 3, 8, 6, 7}
ListNode* head = ...;
int x = 6; // 指定的分割值
// 调用splitList函数
splitList(head, x);
// 打印分割后的链表
printLinkedList(head);
cout << "Small list ends with value less than or equal to x: ";
printLinkedList(smallHead->next); // 打印小数部分链表
return 0;
}
// 辅助函数,打印链表
void printLinkedList(ListNode* head) {
while (head != nullptr) {
cout << head->val << " -> ";
head = head->next;
}
cout << "nullptr" << endl;
}
在这个例子中,main
函数首先初始化链表,并调用splitList
函数进行分割。然后通过printLinkedList
辅助函数分别打印出分割后的两个链表。