用c++写出有一个整数单链表L,设计一个尽可能高效的算法将所有负整数的元素移到其他元素的前面。 例如:L=(1,2,-1,-2,3,-3,4) 移动 后 L=(-1,-2,-3,1,2,3,4)
时间: 2024-10-06 07:06:11 浏览: 0
在C++中,我们可以使用迭代的方式来实现这个算法,因为遍历链表并且修改位置的效率通常优于递归。以下是一个简单的步骤描述:
1. 创建两个指针,`prev` 和 `current`,初始都指向链表的头节点。
2. 创建一个临时指针 `negHead`,用于存放所有的负数节点。
3. 遍历链表,如果当前节点的值小于0,将其从原位置断开并插入到 `negHead` 的前面,然后更新 `prev` 指向该节点;否则,将 `prev` 更新为当前节点。
4. 遍历结束后,将 `negHead` 的下一个节点设为原链表的头节点,完成整个操作。
下面是一个简化的伪代码示例:
```cpp
class ListNode {
public:
int val;
ListNode *next;
};
ListNode* moveNegativesToFront(ListNode* head) {
ListNode* prev = nullptr;
ListNode* negHead = nullptr;
ListNode* current = head;
while (current != nullptr) {
if (current->val < 0) {
if (prev != nullptr) {
prev->next = negHead;
} else {
// 如果链表中第一个节点就是负数,直接设置为新头
head = negHead;
}
negHead = new ListNode(current->val);
negHead->next = negHead->next; // 将原next节点链接到新列表
prev = negHead;
} else {
prev = current;
}
current = current->next;
}
return head;
}
```