假设一个单链表中所有元素为整数,编写算法将所有小于0的元素移动到所有大于0的元素前面,要求算法的时间复杂度为O(n),空间复杂度为O(1)
时间: 2023-05-28 15:07:31 浏览: 31
可以采用双指针的方法,一个指针从链表头开始向后遍历,另一个指针从链表尾开始向前遍历。当两个指针相遇时,遍历结束。
具体算法步骤如下:
1. 定义两个指针:p1指向链表头,p2指向链表尾。
2. 从p1开始向后遍历,直到找到第一个大于0的元素。如果找到了,就将p1指向该元素的位置,否则结束遍历。
3. 从p2开始向前遍历,直到找到第一个小于0的元素。如果找到了,就将p2指向该元素的位置,否则结束遍历。
4. 如果p1和p2都找到了对应的元素,就将它们交换位置,并继续向后、向前遍历,直到p1和p2相遇为止。
5. 最后,所有小于0的元素都会移动到所有大于0的元素前面。
代码实现如下:
```
void move(ListNode* head) {
ListNode* p1 = head;
ListNode* p2 = head;
while (p1 != p2) {
while (p1 && p1->val >= 0) { // 找到第一个小于0的元素
p1 = p1->next;
}
while (p2 && p2->val < 0) { // 找到第一个大于等于0的元素
p2 = p2->next;
}
if (p1 && p2) { // 交换p1和p2对应的元素
int tmp = p1->val;
p1->val = p2->val;
p2->val = tmp;
}
}
}
```
时间复杂度为O(n),空间复杂度为O(1)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)