算法设计题:有一个整数单链表L,设计一个尽可能高效算法将所有负整数的元素移到其他元素的前面。例如,L=(1,2,-1,-2,3,-3,4),移动后L=(-1,-2,-3,1,2,3,4)
时间: 2023-05-14 08:05:42 浏览: 261
可以使用双指针法,一个指针指向当前处理的节点,另一个指针指向已经处理好的负整数的最后一个节点。遍历整个链表,如果当前节点是负整数,则将其插入到负整数的最后一个节点之后,并更新负整数的最后一个节点。最后,所有负整数都被移到了链表的前面。以下是示例代码:
```python
def move_negative_numbers(head):
if not head:
return None
neg_tail = None
curr = head
while curr:
if curr.val < 0:
if not neg_tail:
neg_tail = curr
else:
neg_tail.next = curr
neg_tail = curr
curr = curr.next
if neg_tail:
neg_tail.next = head
return neg_tail
else:
return head
```
对于输入的链表L,可以先将其转化为一个链表,然后调用上述函数进行处理。
相关问题
有一个整数单链表表L,设计一个尽可能高效的Java算法将所有负整数的元素移到其它元素的前面。
可以使用两个指针来实现这个算法。一个指针用于遍历链表,另一个指针用于记录负整数的位置。具体步骤如下:
1. 初始化两个指针,一个指向链表的头节点,另一个指向链表的第一个负整数节点(初始时为null)。
2. 遍历链表,对于每个节点:
- 如果节点的值为负整数,将其移到负整数节点之前,并更新负整数节点的位置。
- 否则,继续遍历下一个节点。
3. 返回移动后的链表。
以下是Java代码示例:
```java
public class Solution {
public ListNode moveNegativeNumbers(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode negNode = null; // 负整数节点
ListNode curr = head; // 当前节点
ListNode prev = null; // 当前节点的前一个节点
while (curr != null) {
if (curr.val < 0) {
if (prev != null) {
prev.next = curr.next; // 将当前节点从链表中移除
} else {
head = curr.next; // 更新头节点
}
if (negNode == null) {
curr.next = head; // 将当前节点插入到头部
head = curr;
} else {
curr.next = negNode.next; // 将当前节点插入到负整数节点之后
negNode.next = curr;
}
negNode = curr; // 更新负整数节点的位置
curr = prev.next; // 继续遍历下一个节点
} else {
prev = curr;
curr = curr.next;
}
}
return head;
}
}
```
2.有一个整数单链表表L,设计一个尽可能高效的算法将所 有负整数的元素移到其它元素的前面。
要将所有负整数的元素移到其他元素的前面,可以使用两个指针来实现。一个指针用于遍历链表,另一个指针用于记录当前位置。
具体算法如下:
1. 初始化两个指针,一个指向链表的头节点,另一个指向链表的第一个非负整数节点(初始时可以指向空节点)。
2. 遍历链表,对于每个节点:
- 如果节点的值为负整数,将其移到第一个非负整数节点之前,并更新第一个非负整数节点的位置。
- 如果节点的值为非负整数,继续遍历下一个节点。
3. 遍历完成后,所有负整数的元素都会被移到第一个非负整数节点之前。
以下是算法的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def moveNegativeElements(head):
if not head or not head.next:
return head
dummy = ListNode(0) # 创建一个虚拟头节点
dummy.next = head
prev_positive = dummy # 记录第一个非负整数节点的位置
curr = head
while curr:
if curr.val < 0:
# 将当前节点移到第一个非负整数节点之前
prev_positive.next = curr.next
curr.next = dummy.next
dummy.next = curr
curr = prev_positive.next
else:
prev_positive = curr
curr = curr.next
return dummy.next
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![md](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)