有一个整数单链表表L,设计一个尽可能高效的Java算法将所有负整数的元素移到其它元素的前面。
时间: 2024-06-15 17:05:34 浏览: 120
可以使用两个指针来实现这个算法。一个指针用于遍历链表,另一个指针用于记录负整数的位置。具体步骤如下:
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;
}
}
```
阅读全文