有一个整数单链表L,设计一个尽可能高效算法将所有负整数的元素移到其他元素的前面。并给出算法的时间复杂度和空间复杂度。java代码
时间: 2024-10-08 16:21:28 浏览: 22
要实现这个功能,我们可以使用两个指针,一个`prev`用于存储当前遍历到的节点(正数),另一个`cur`遍历整个链表。遍历时,如果遇到负数,就将`prev`指向的节点移动到链表头部,然后更新`prev`为当前节点。当遍历完整个链表后,`prev`指向的就是所有正数的尾部。
以下是一个简单的Java代码实现:
```java
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode reorderList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = null, current = head;
while (current != null) {
ListNode nextTemp = current.next;
if (current.val < 0) {
if (prev == null) {
head = current;
} else {
prev.next = current;
}
current.next = head;
head = current;
} else {
prev = current;
}
current = nextTemp;
}
prev.next = null; // 如果所有元素都是负数,prev就是正数链表的最后一个节点
return head;
}
}
```
时间复杂度分析:此算法的时间复杂度是O(n),其中n是链表中的元素数量。因为我们只遍历了一次链表。
空间复杂度分析:空间复杂度是O(1),因为这里没有使用额外的数据结构,除了几个临时变量,我们只是修改了原有链表的部分连接关系。
阅读全文