使用单链表L存储一批整数(值均不为0),请设计算法,将L中的所有的负数放在正数之前。
时间: 2023-03-28 16:04:34 浏览: 59
可以回答这个问题。具体算法如下:
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;
}
}
}
相关问题
使用单链表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中的所有的负数放在正数之前
可以使用双指针法,一个指针从链表头开始,一个指针从链表尾开始,分别向中间移动,直到两个指针相遇为止。在移动过程中,如果头指针指向的节点的值为负数,则继续向后移动;如果尾指针指向的节点的值为正数,则继续向前移动;如果头指针指向的节点的值为正数,尾指针指向的节点的值为负数,则交换两个节点的值。直到两个指针相遇为止,整个链表中的负数就都在正数之前了。