有一个整数单链表L，设计一个尽可能高效算法将所有负整数的元素移到其他元素的前面。并给出算法的时间和空间复杂度，程序

你可以采用双指针法来解决这个问题，即使用两个指针，一个快指针p正常遍历链表，另一个慢指针s用于遍历链表并将遇到的负数移到新的位置。当遇到正数时，更新快指针，继续前进；当遇到负数时，移动慢指针到当前位置，并将其插入到已排序的负数链表前部。最后，快指针所在的节点就是新链表的结束。

伪代码如下：

def move_negatives_to_front(L):
    head = ListNode(0)  # 创建一个虚拟头节点，方便操作
    fast = L
    slow = L

    negative_head = None  # 负数链表的头节点
    is_negative = False   # 标记是否当前节点为负数

    while fast is not None:
        if fast.val < 0 and not is_negative:  # 遇到第一个负数
            is_negative = True
            negative_head = fast
        elif fast.val >= 0 or (is_negative and fast.val < 0):  # 正数或后续负数
            if is_negative:  # 如果是负数，则移动到前面
                new_node = ListNode(fast.val)
                new_node.next = negative_head.next
                negative_head.next = new_node
            fast = fast.next
        else:  # 同样是负数，直接跳过
            fast = fast.next
        slow = slow.next

    # 连接正数链表和负数链表
    if negative_head is not None:
        negative_head.next = head.next
    return head.next  # 返回新链表的头节点

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

时间复杂度：O(n)，其中n是链表的长度，因为我们需要遍历整个链表一次。
空间复杂度：O(1)，除了原始链表，我们只用了常数级别的额外空间用于指针和临时节点。