372. Rearrange Linked List — Negatives Before Positives

Given a linked list of integers, rearrange it so that all negative values appear before all non-negative values (zero counts as non-negative), preserving the relative order within each group. Return the result as an array.

Input: An array of node values.

Output: Array — negatives first, then non-negatives.

Examples

Input: [1,-2,3,-4,5]
Output: [-2,-4,1,3,5]
Explanation: Negatives first, order preserved.

Input: [-1,-2,-3]
Output: [-1,-2,-3]
Explanation: All negative.

Input: [1,2,3]
Output: [1,2,3]
Explanation: No negatives.

Constraints

• 0<=n<=10^5
• -10^9<=value<=10^9

Asked by