某非空单链表L中的所有元素为整数,设计一个算法,将所有小于0的结点移到所有大于或等于0的结点的前面。L={1,3,-4,6,2,1,-2,3,5}.用c语言
时间: 2024-10-10 21:14:55 浏览: 18
在C语言中,我们可以使用两个指针,一个指向当前节点,另一个指向上一个遇到的非负节点,同时遍历链表。以下是实现这个算法的步骤:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 插入节点到链表
ListNode* insertNode(ListNode* head, int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = head;
return newNode;
}
// 合并小于0和大于等于0的部分
void moveNegativesToFront(ListNode** head) {
if (*head == NULL || (*head)->val >= 0) {
return; // 如果链表为空或头节点是非负的,直接返回
}
ListNode* current = *head;
ListNode* prevNonNeg = NULL;
while (current != NULL) {
if (current->val >= 0) { // 找到非负节点
if (prevNonNeg != NULL) {
prevNonNeg->next = current;
} else {
*head = current; // 将非负节点移动到头部
}
prevNonNeg = current;
}
current = current->next;
}
if (prevNonNeg != NULL) { // 链表末尾可能是负值,连接到新链表末尾
prevNonNeg->next = *head;
}
}
// 打印链表
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->val);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
ListNode* head = NULL;
head = insertNode(head, 1);
head = insertNode(head, 3);
head = insertNode(head, -4);
head = insertNode(head, 6);
head = insertNode(head, 2);
head = insertNode(head, 1);
head = insertNode(head, -2);
head = insertNode(head, 3);
head = insertNode(head, 5);
printf("Original List:\n");
printList(head);
moveNegativesToFront(&head);
printf("\nAfter moving negatives to front:\n");
printList(head);
return 0;
}
```
当运行这段代码后,原始链表`{1, 3, -4, 6, 2, 1, -2, 3, 5}`会被修改成`{-4, 1, 1, -2, 3, 3, 6, 2, 5}`。