C语言写代码:将单链表按基准划分。以单链表的首结点值x为基准将该单链表分割为两部分,使所有小于x的结点排在大于或等于x的结点之前。
时间: 2024-10-09 10:03:53 浏览: 60
在C语言中,你可以通过遍历链表并维护两个指针,一个指向当前节点,另一个用于存放大于等于基准值的节点,来实现这个功能。下面是一个简单的步骤描述:
1. 首先,定义两个指针,`current` 和 `equalOrGreater`, 分别初始化为链表头结点和NULL。
2. 然后开始遍历链表:
a. 检查当前节点的值是否小于基准值 `x`。
b. 如果小于,更新 `current` 的下一个节点,并将其作为新的当前节点继续遍历。如果 `current` 为空,说明这是第一个元素,直接跳过。
c. 否则(即当前节点值大于等于 `x`),将 `current` 节点连接到 `equalOrGreater` 指向的链表之后,然后将 `equalOrGreater` 更新为 `current`,以便后续存储更大值的节点。
d. 遍历结束后,`equalOrGreater` 就会指向大于等于 `x` 的链表的头部。
以下是伪代码的形式表示:
```c
struct ListNode* divideList(struct ListNode* head, int x) {
if (!head || !head->next) return head; // 空链表或只有一个元素的情况
struct ListNode* current = head;
struct ListNode* equalOrGreater = NULL;
while (current) {
if (current->val < x) {
current = current->next;
} else {
if (!equalOrGreater) { // 当前链节是第一个大于等于x的节点
equalOrGreater = current;
} else {
// 将current添加到equalOrGreater的后面
struct ListNode* nextTemp = equalOrGreater->next;
equalOrGreater->next = current;
current->prev = equalOrGreater;
equalOrGreater = nextTemp;
}
current = current->next;
}
}
// 如果链表中没有小于x的节点,则原地返回
if (equalOrGreater == head) {
return head;
}
// 返回大于等于x的部分的头节点
return equalOrGreater;
}
```
阅读全文