带头结点的单链表L中所有元素为整数,设计一个算法将所有小于零的节点移到所有大于等于零的节点的前面。
时间: 2024-11-06 08:19:42 浏览: 20
要实现这个功能,我们可以使用两个指针,一个指向当前检查的节点(`current`),另一个指向头节点(`prev`)。遍历整个链表,当遇到一个负数时,我们需要将其插入到正数序列的前面。以下是C语言中的算法步骤:
1. 初始化两个指针 `current = head` 和 `prev = NULL`,分别表示链表头部和上一个已处理的节点。
2. 当 `current` 不为空时,执行以下操作:
a. 检查 `current` 的值是否小于0:
- 如果 `current->data < 0`,则创建一个新的节点 `new_node`,其值为 `current->data` 并链接到 `head` 前面。
- 更新 `head` 指向新节点,然后更新 `prev` 为新节点。
- 将 `current` 移动到下一个节点。
b. 如果 `current->data >= 0`,则不需要做任何特殊操作,直接将 `current` 移动到下一个节点。
3. 遍历结束后,`current` 应该已经到达了链表末尾。
下面是对应的C语言代码实现:
```c
struct ListNode {
int data;
struct ListNode* next;
};
void moveNegativeToFront(struct ListNode* head) {
if (head == NULL || head->next == NULL || head->data >= 0) {
return; // 如果链表空或只有一个节点或者首节点非负,则无需移动
}
struct ListNode* new_head = new ListNode(head->data);
struct ListNode* prev = new_head;
struct ListNode* current = head->next;
while (current != NULL) {
if (current->data < 0) {
prev->next = current;
new_head->next = current->next;
current->next = new_head;
new_head = current;
} else {
prev = current;
}
current = current->next;
}
if (new_head != head) { // 如果有负数,修改头节点
head->next = new_head->next;
}
}
```
阅读全文