使用单链表L存储一批整数(值均不为0),请设计算法,将L中的所有的负数放在正数之前。
时间: 2023-03-28 13:04:36 浏览: 60
好的,我可以回答这个问题。可以使用两个指针,一个指向当前处理的节点,另一个指向当前处理的节点的前一个节点。从头节点开始遍历链表,如果当前节点的值为负数,则将其插入到前一个节点的后面,同时更新指针。如果当前节点的值为正数,则继续向后遍历。最终,所有的负数都会被移到正数的前面。
相关问题
使用单链表L存储一批整数(值均不为0),请设计算法,将L中的所有负数放在正数之前
可以使用两个指针p和q,p指向链表头节点,q指向p的下一个节点。从头节点开始遍历链表,如果p指向的节点的值为负数,则将p指向的节点插入到链表头节点的前面,同时p和q都向后移动一位;如果p指向的节点的值为正数,则只将p向后移动一位。直到p指向链表尾节点时,遍历结束,负数都被移到了链表头节点的前面。
具体实现如下:
void moveNegativeToFront(ListNode* L) {
ListNode* p = L->next;
ListNode* q = p->next;
while (q != NULL) {
if (p->val < ) {
p->next = q->next;
q->next = L->next;
L->next = q;
q = p->next;
} else {
p = q;
q = q->next;
}
}
}
使用单链表L存储一批整数(值均不为0),请设计算法,将L中的所有的负数放在正数之前
可以使用双指针法,一个指针从链表头开始,一个指针从链表尾开始,分别向中间移动,直到两个指针相遇为止。在移动过程中,如果头指针指向的节点的值为负数,则继续向后移动;如果尾指针指向的节点的值为正数,则继续向前移动;如果头指针指向的节点的值为正数,尾指针指向的节点的值为负数,则交换两个节点的值。直到两个指针相遇为止,整个链表中的负数就都在正数之前了。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://img-home.csdnimg.cn/images/20210720083646.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)