使用单链表L存储一批整数(值均不为0),请设计算法,将L中的所有的负数放在正数之前。
时间: 2023-03-28 18:04:34 浏览: 85
已知线性表按顺序存于内存,每个元素都是整数,试设计把所有值为负数的元素移到全部正数值元素前边的算法 .cpp
可以回答这个问题。具体算法如下:
1. 定义两个指针p和q,分别指向链表的头结点和第一个正数结点。
2. 从头结点开始遍历链表,如果当前结点的值为负数,则将其插入到q结点之前,并更新q指针。
3. 遍历完链表后,所有负数结点都已经插入到正数结点之前,链表的顺序也被调整了。
代码实现如下:
void moveNegativeBeforePositive(ListNode* L) {
ListNode *p = L, *q = L;
while (p != NULL) {
if (p->val < ) {
ListNode *tmp = p;
p = p->next;
tmp->next = q;
q = tmp;
} else {
p = p->next;
}
}
}
阅读全文