某非空单链表l中所有元素为整数,设计一个算法将所有小于零的节点移到所有大于等于零的节点的前面。
时间: 2023-05-31 10:19:16 浏览: 237
### 回答1:
可以使用两个指针p和q,p指向当前已经处理好的小于零的节点的末尾,q指向当前正在处理的节点。初始时,p指向头节点,q指向第二个节点。
从第二个节点开始遍历链表,如果当前节点的值小于零,则将其插入到p的后面,并更新p的位置;否则,将q向后移动一位。
最后,所有小于零的节点都被移到了大于等于零的节点的前面。
具体实现可以参考下面的代码:
void moveNegativeNodesToFront(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
ListNode* p = head;
ListNode* q = head->next;
while (q != nullptr) {
if (q->val < ) {
// 将q插入到p的后面
ListNode* tmp = q;
q = q->next;
tmp->next = p->next;
p->next = tmp;
p = tmp;
} else {
q = q->next;
}
}
}
### 回答2:
这道题可以采用一趟扫描加上双指针的思路来解决。具体流程如下:
1.定义两个指针p和q,初始时p和q指向链表的头结点l->next。
2.首先移动指针p,找到第一个大于等于零的节点,也就是第一个需要插入小于零节点的位置。如果p指向空节点,则说明所有节点都小于零,遍历结束。
3.移动指针q,找到第一个小于零的节点,也就是需要插入到p位置之前的节点。
4.如果找到了p和q,插入q节点到p节点之前,并更新p和q指向下一个节点。如果没找到q节点,则说明所有小于零的节点都已经移动到链表的前面,遍历结束。
5.重复步骤2~4,直到找到所有满足条件的节点为止。
完整代码如下:
void move_negative(ListNode* l){
ListNode* p = l->next; //指向链表头结点
while(p != NULL){ //遍历链表
if(p->data >= 0){ //找到第一个大于等于零的节点
ListNode* q = p->next; //从下一个节点开始遍历
while(q != NULL){ //查找小于零的节点
if(q->data < 0){ //找到了小于零的节点
//删除q节点并插入到p节点的前面
p->next = q->next;
q->next = l->next;
l->next = q;
q = p->next; //更新q指向下一个节点
}
else{ //继续查找下一个节点
q = q->next;
}
}
return; //找完了所有小于零的节点,结束遍历
}
else{ //继续查找下一个大于等于零的节点
p = p->next;
}
}
}
时间复杂度为O(n),空间复杂度为O(1)。
### 回答3:
这道题目要求我们在一个非空单链表中将所有小于零的节点移到所有大于等于零的节点的前面。我们可以利用两个指针p和q分别指向头节点和当前节点,遍历整个链表,将小于零的节点插入到大于等于零的节点前面即可。
具体实现如下:
1. 初始化两个指针p和q,分别指向头节点和当前节点。
2. 遍历整个链表,当q指向小于零的节点时,将该节点插入到p所指向的节点之前,并移动p指针;否则,只移动q指针即可。
3. 遍历结束后,p所指向的节点为第一个大于等于零的节点,所有小于零的节点已经插入到大于等于零的节点之前。
4. 返回链表头节点即可。
具体实现代码如下:
Node* moveNegativeNodes(Node* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
Node *p = head, *q = head->next;
while (q != nullptr) {
if (q->val < 0) {
p->next = q->next;
q->next = head;
head = q;
q = p->next;
} else {
p = q;
q = q->next;
}
}
return head;
}
以上就是本题的全部解析了,通过双指针遍历链表,将小于零的节点插入到大于等于零的节点之前,时间复杂度为O(n),空间复杂度为O(1)。