From Absolute Order to Actual Order

Medium

You are given head, the first node of a non-empty singly linked list. Its values are in non-decreasing order of their **absolute values**, for example 0, 2, -3, 3, -8. Rearrange the list so that the values are in non-decreasing order of their actual values, and return its first node. Sorting in O(n log n) is the easy way out. Try to do it in O(n) by using how the input list is arranged.

Example 1

head=list_node([1, -2, 3, -3, -7]) → [-7, -3, -2, 1, 3]

By absolute value the list is in order: 1, 2, 3, 3, 7. By actual value the order is -7, -3, -2, 1, 3.

Example 2

head=list_node([0, 4, 4]) → [0, 4, 4]

There are no negative values, so the list is already in order.

Example 3

head=list_node([-6]) → [-6]

Constraints

The list has between 1 and 10⁵ nodes
-5000 ≤ Node.val ≤ 5000
The absolute values are in non-decreasing order

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Linked List Two Pointers Sorting

Similar problems

Sorting a Linked List Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Drop the K-th Node From the Tail Medium

Input

head=list_node([1, -2, 3, -3, -7])

Expected

[-7, -3, -2, 1, 3]

Run checks the first 3 tests in your browser. Submit checks all 36 tests on the server, hidden ones included.