用cpp将单链表按基准划分。以单链表的首结点值x为基准将该单链表分割为两部分,使所有小于x的结点排在大于或等于x的结点之前
时间: 2024-10-17 08:08:08 浏览: 23
在C++中,你可以通过遍历链表的方式来分割它,创建两个新的链表:一个存储小于基准值`x`的节点,另一个存储大于等于`x`的节点。这里是一个简单的示例,假设你已经有了一个名为`ListNode`的链表节点结构,并且有一个指向链表头部的指针`head`:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* splitList(ListNode* head, int x) {
ListNode *lessThanX = nullptr, *greaterOrEqualX = nullptr; // 创建两个新链表
ListNode *current = head;
while (current != nullptr) {
if (current->val < x) { // 小于x的节点
lessThanX = new ListNode(current->val); // 新建节点并连接到lessThanX链表
lessThanX->next = lessThanX ? lessThanX->next : head;
head = lessThanX;
} else { // 大于等于x的节点
greaterOrEqualX = current; // 当前节点进入greaterOrEqualX链表
}
current = current->next;
}
return greaterOrEqualX; // 返回大于等于x的链表头
}
```
在这个函数中,我们先初始化两个空链表,然后逐个遍历原始链表。如果当前节点的值小于`x`,我们就创建一个新的`ListNode`并将它添加到`lessThanX`链表中;否则,我们将当前节点设置为`greaterOrEqualX`。最后返回`greaterOrEqualX`作为新链表的头。
阅读全文