某非空单链表L中的所有元素为整数,设计一个算法,用C语言将所有小于0的结点移到所有大于或等于0的结点的前面。
时间: 2024-10-08 22:18:52 浏览: 55
为了在C语言中设计这个算法,我们可以使用迭代的方式遍历链表,并同时维护两个指针,一个指向当前节点(positive),另一个用于存储小于0的节点(negative)。我们会在遍历时做以下几个步骤:
1. 初始化两个指针,`current` 和 `negative` 都设置为链表的头节点;
2. 当 `current` 非空且值小于0时,将 `negative` 的下一个节点指向 `current`,然后 `current` 移动到下一个节点;
3. 否则,如果 `current` 的值大于或等于0,则直接移动 `current` 到下一个节点;
4. 当遍历完链表,`negative` 指向的就是所有小于0的节点的最后一个。这时,可以将 `negative` 节点设为新链表的头,然后从 `negative->next` 开始连接剩余的正常顺序的正数节点。
以下是伪代码形式的算法描述:
```c
struct ListNode *splitList(struct ListNode* head) {
struct ListNode* positive = head;
struct ListNode* negative = NULL;
while (head != NULL) {
if (head->val < 0) {
if (negative == NULL) {
negative = head;
}
head->next = negative->next;
negative->next = current;
} else {
current = head;
}
head = head->next;
}
if (negative != NULL) {
negative->next = positive; // 将负数链接在正数链的头部
return negative;
} else {
return positive;
}
}
```
阅读全文