Skip to main content
Talentd

Sort Linked List Already Sorted Using Absolute Values - Solution & Explanation

MediumPremiumFree on FleetCodeLinked ListTwo PointersSorting7 min read
Practice this problem

Problem Statement

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, 105].
  • -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?

Approach Overview

Problem Overview: The linked list is sorted by absolute values, not by the actual values. Negative numbers may appear after positives because their absolute values are smaller. Your task is to reorder the list so it becomes correctly sorted by the real values while keeping the operation efficient.

Approach 1: Convert to Array and Sort (O(n log n) time, O(n) space)

Traverse the linked list and copy all node values into an array. Sort the array using a standard sorting algorithm, then rebuild the linked list or overwrite the node values in sorted order. This approach works for any list regardless of structure and is easy to implement. However, it ignores the special property that the list is already sorted by absolute value, which means it does extra work compared to the optimal solution.

Approach 2: Head Insertion Method (O(n) time, O(1) space)

The key observation: because the list is sorted by absolute value, all negative values appear in reverse order relative to their correct sorted positions. For example, a sequence like 1 → -2 → -3 → 4 means the negatives must be moved toward the front. Iterate through the list while maintaining a pointer to the previous node. Whenever you encounter a negative node that appears after a positive segment, detach it and insert it at the head of the list. This is essentially a controlled reordering using pointer manipulation.

The process only requires pointer updates: remove the current negative node (prev.next = curr.next) and push it to the front (curr.next = head, then update head). Because each node is visited once and moved at most once, the algorithm runs in linear time. No extra memory is needed beyond a few pointers.

This technique is closely related to pointer manipulation patterns used in two pointers and in-place transformations in sorting problems on linked lists. Instead of re-sorting the entire structure, you exploit the ordering constraint already present in the input.

Recommended for interviews: The head insertion method is the expected solution. Interviewers want you to notice the special ordering by absolute value and convert it into a linear-time transformation using pointer manipulation. The array + sort approach demonstrates baseline understanding, but the O(n) in-place method shows strong linked list reasoning and algorithmic insight.

Solution

We first assume that the first node is already sorted. Starting from the second node, when we encounter a node with a negative value, we use the head insertion method. For non-negative values, we continue to traverse down.

The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Copy to Array and SortO(n log n)O(n)Simple implementation when constraints are small or when ignoring the absolute-value property
Head Insertion MethodO(n)O(1)Optimal solution that exploits the list being sorted by absolute values

Video Solution

leetcode 2046. Sort Linked List Already Sorted Using Absolute Values - linear traversal with check • Code-Yao • 169 views views

Watch 2 more video solutions →

Frequently Asked Questions

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.
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.
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.

Ready to solve this problem?

Practice Sort Linked List Already Sorted Using Absolute Values with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort List