Is Sort Linked List Already Sorted Using Absolute Values easy or hard?

This problem is typically rated Medium. The implementation is short, but the challenge is recognizing that the list is sorted by absolute values and that negative numbers appear in reverse order. Once that insight is clear, the head insertion approach becomes straightforward.

Sort Linked List Already Sorted Using Absolute Values Python/Java solution

Most implementations follow the same idea across languages: maintain previous and current pointers, detach negative nodes, and insert them at the head. This pointer-based approach works in Python, Java, C++, Go, and TypeScript with O(n) time and O(1) space.

What is the best approach for Sort Linked List Already Sorted Using Absolute Values?

The best approach is the head insertion method. Traverse the linked list once and whenever you encounter a negative node that should appear earlier in sorted order, detach it and insert it at the head. This works because the list is already sorted by absolute values. The algorithm runs in O(n) time with O(1) extra space.

Is Sort Linked List Already Sorted Using Absolute Values asked at Google/Amazon/Meta?

Linked list transformation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The focus is usually on pointer manipulation, recognizing ordering properties, and achieving O(n) time with O(1) extra space.

What data structure is used in Sort Linked List Already Sorted Using Absolute Values?

The problem uses a singly linked list as the main data structure. The optimal solution relies on pointer manipulation within the linked list, sometimes combined with a two-pointer style traversal using current and previous node references.

What is the time complexity of Sort Linked List Already Sorted Using Absolute Values?

The optimal solution runs in O(n) time because each node in the linked list is visited once and moved at most once. Space complexity is O(1) since the algorithm only uses a few pointers and performs in-place node rearrangement.

Description Hints 3 Solution Video 10:01

2046. Sort Linked List Already Sorted Using Absolute Values

Q: How to solve Sort Linked List Already Sorted Using Absolute Values in O(n)?

Use the head insertion technique. Iterate through the list and track the previous node. When a negative value appears that should be placed earlier, remove it from its position and insert it at the front of the list. Because the list is already ordered by absolute values, this single pass correctly produces a fully sorted list.

Medium67.1% acceptancePremium elsewhere, free here

Given the head of a singly linked list that is sorted in non-decreasing order using the absolute values of its nodes, return the list sorted in non-decreasing order using the actual values of its nodes.

Example 1:

Input: head = [0,2,-5,5,10,-10]
Output: [-10,-5,0,2,5,10]
Explanation:
The list sorted in non-descending order using the absolute values of the nodes is [0,2,-5,5,10,-10].
The list sorted in non-descending order using the actual values is [-10,-5,0,2,5,10].

Example 2:

Input: head = [0,1,2]
Output: [0,1,2]
Explanation:
The linked list is already sorted in non-decreasing order.

Example 3:

Input: head = [1]
Output: [1]
Explanation:
The linked list is already sorted in non-decreasing order.

Constraints:

The number of nodes in the list is the range [1, 10⁵].
-5000 <= Node.val <= 5000
head is sorted in non-decreasing order using the absolute value of its nodes.

Follow up:

Can you think of a solution with O(n) time complexity?

Topics

Hints open one at a time

Hint 1

The nodes with positive values are already in the correct order.

Hint 2

Nodes with negative values need to be moved to the front.

Hint 3

Nodes with negative values are in reversed order.

10:01

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

2046. Sort Linked List Already Sorted Using Absolute Values

Topics

Hints open one at a time

Similar problems