某非空单链表l中所有元素为整数,设计一个算法将所有小于零的结点移到所有大于等于零的结点的前面。
时间: 2023-05-31 12:19:26 浏览: 257
已知线性表按顺序存于内存,每个元素都是整数,试设计把所有值为负数的元素移到全部正数值元素前边的算法 .cpp
### 回答1:
可以使用双指针法,定义两个指针p和q,初始时p指向链表头结点,q指向第一个大于等于零的结点。然后遍历链表,如果当前结点的值小于零,就将其插入到q结点之前,同时更新p和q指针的位置。具体实现如下:
1. 如果链表为空或只有一个结点,则直接返回。
2. 定义指针p和q,初始时p指向链表头结点,q指向第一个大于等于零的结点。
3. 遍历链表,如果当前结点的值小于零,就将其插入到q结点之前,同时更新p和q指针的位置。具体步骤如下:
a. 如果当前结点的值小于零,就将其从链表中删除,并将其插入到q结点之前。
b. 更新p指针的位置,使其指向下一个结点。
c. 如果q指针指向的结点的值小于零,就更新q指针的位置,使其指向下一个大于等于零的结点。
4. 遍历结束后,所有小于零的结点都已经移到了所有大于等于零的结点的前面。
下面是具体的代码实现:
void moveNegativeNodes(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
ListNode* p = head;
ListNode* q = head;
while (p != nullptr) {
if (p->val < 0) {
ListNode* temp = p;
p = p->next;
temp->next = q;
head = temp;
q = temp;
} else {
q = p;
p = p->next;
if (q->val >= 0) {
break;
}
}
}
}
### 回答2:
题目描述
本题要求从一个非空单链表中移动所有小于零的结点到所有大于等于零的结点的前面。
解题思路
我们可以新建两个链表,一个用于存储小于零的结点,另一个用于存储大于等于零的结点。遍历原链表,将小于零的结点插入到小链表最后,将大于等于零的结点插入到大链表最后。最后将小链表连在大链表之前即可。
伪代码
1. 初始化两个空链表,分别用于存储小于零的结点和大于等于零的结点
2. 遍历原链表,如果当前结点的值小于零,则将其插入到小链表的最后,否则将其插入到大链表的最后。
3. 将小链表连在大链表之前。
Python代码
```
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def move_list(head: ListNode) -> ListNode:
if not head:
return None
dummy_small = ListNode(0)
dummy_big = ListNode(0)
small, big = dummy_small, dummy_big
while head:
if head.val < 0:
small.next = head
small = small.next
else:
big.next = head
big = big.next
head = head.next
big.next = dummy_small.next
small.next = None
return dummy_big.next
```
时间复杂度
遍历一遍原链表,时间复杂度为 O(n)。
空间复杂度
新建两个链表,所以空间复杂度为 O(n)。
总结
本题解法比较简单,只需要新建两个链表,然后遍历原链表插入到对应的链表中,最后将小链表连在大链表之前就可以了。但是需要注意边界条件的处理。
### 回答3:
题目描述
本文的题目是设计一个算法,将非空单链表l中所有小于零的结点移到所有大于等于零的结点的前面。
思路分析
本题的主要思路是使用双指针的方法,一前一后查找链表中的节点。定义两个指针slow和fast,slow指向链表的头结点,fast指向链表的第二个结点。如果slow指向的节点的值小于0,就继续查找下一个节点;如果fast指向的节点的值大于等于0,就将slow指向的节点和fast指向的节点交换。
具体来说,如果slow指向的节点的值小于0,就令slow=slow.next。如果fast指向的节点的值大于等于0,就将slow指向的节点和fast指向的节点交换,并同时令slow=slow.next。
算法实现
public ListNode partition(ListNode head) {
if(head==null) return null;
ListNode slow=head;
ListNode fast=head.next;
while(fast!=null){
if(fast.val>=0){
//将slow指向的节点和fast指向的节点交换
int tmp=slow.val;
slow.val=fast.val;
fast.val=tmp;
slow=slow.next;
}
fast=fast.next;
}
return head;
}
时间复杂度
本算法的时间复杂度为O(n),其中n表示链表的节点数。因为要遍历链表中的所有节点,并进行元素交换,所以算法的时间复杂度为n。
总结
本文介绍了如何将非空单链表中的所有小于零的结点移到所有大于等于零的结点的前面。算法使用双指针的方法,一前一后查找链表中的节点,然后进行元素交换。本算法的时间复杂度为O(n)。
阅读全文