用c++代码某非空单链表L中所有元素为整数,设计一个算法将所有小于零的节点移到所有大于等于零的节点的前面。
时间: 2024-09-29 11:07:18 浏览: 41
在C++中,你可以通过遍历链表,并在遍历过程中判断每个节点的值,将小于0的节点插入到大于等于0的节点之前。这里有一个简单的算法示例:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点结构
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* separatePositiveAndNegative(ListNode* head) {
if (head == nullptr || head->val >= 0) { // 如果头节点为空或者其值非负,则直接返回
return head;
}
ListNode* negativeHead = new ListNode(head->val); // 创建一个新的头节点存放负值
ListNode* negativeTail = negativeHead; // 负值链表的尾部指针
ListNode* positiveHead = head; // 正值链表的头部指针
while (positiveHead != nullptr && positiveHead->next != nullptr) { // 遍历正向链表
ListNode* nextNode = positiveHead->next;
if (nextNode->val < 0) { // 当找到负值时,将其添加到负值链表
negativeTail->next = nextNode;
negativeTail = nextNode;
} else { // 否则将当前节点移动到下一个正向节点
positiveHead = positiveHead->next;
}
}
// 连接正负链表
negativeTail->next = positiveHead;
return negativeHead;
}
int main() {
// 示例链表:1 -> -3 -> 5 -> -3);
list->next->next = new ListNode(5);
list->next->next->next = new ListNode(-2);
list->next->next->next->next = new ListNode(4);
ListNode* separatedList = separatePositiveAndNegative(list);
while (separatedList != nullptr) {
cout << separatedList->val << " ";
separatedList = separatedList->next;
}
return 0;
}
```
阅读全文