2046. Sort Linked List Already Sorted Using Absolute Values - Detailed Explanation

Problem Statement

You’re given the head of a singly‑linked list that is sorted in non‑decreasing order by the absolute values of its nodes. Your task is to reorder the list so that it is sorted in non‑decreasing order by the actual values of its nodes, then return the new head.

Example 1

Input:  head = [0,2,-5,5,10,-10]
Output: [-10,-5,0,2,5,10]
Explanation:  
 Absolute‑sorted:  [0,2,-5,5,10,-10]  
 Value‑sorted:     [-10,-5,0,2,5,10]

Example 2

Input:  head = [0,1,2]
Output: [0,1,2]
Explanation: list is already sorted by value.

Example 3

Input:  head = [1]
Output: [1]
Explanation: single node.

Constraints

• The number of nodes is in the range [1, 10⁵].
• –5000 ≤ Node.val ≤ 5000
• Input list is sorted by non‑decreasing absolute values.

Hints

1. Negative numbers appear in reverse order among themselves (because their absolutes were sorted).
2. You can “pluck out” any negative node and insert it at the head in O(1).

Brute‑Force Approaches

1. Insertion Sort on Linked List (O(n²))
   • Iterate through the list, for each node remove it and insert into the proper spot in a new sorted list.
2. Merge Sort on Linked List (O(n log n))
   • Standard divide‑and‑conquer list sort.

Optimal O(n) Head‑Insertion Approach

Because all negative values are in reverse order at the front portion of the list, you can scan once and move each negative node to the head as you see it:

1. Initialize two pointers:
   • prev = head
   • curr = head.next
2. While curr is not null:
   • If curr.val < 0:
     • Splice curr out: prev.next = curr.next
     • Insert curr at front:

       curr.next = head
       head = curr
       

     • Advance curr = prev.next
   • Else (non‑negative):
     • prev = curr
     • curr = curr.next
3. Return head.

Step‑by‑Step Walkthrough

Take [0, 2, –5, 5, 10, –10]:

• Start head=0→2→…, prev=0, curr=2 → 2≥0 so move both.
• prev=2, curr=–5 → negative: splice out and insert at front → head becomes –5→0→2→…; now curr=prev.next points to 5.
• 5≥0 → advance → now prev=5, curr=10.
• 10≥0 → advance → now prev=10, curr=–10.
• –10<0 → splice & insert → head=–10→–5→0→2→5→10; curr = prev.next = null.
• Done.

Complexity Analysis

• Time: O(n) — single pass.
• Space: O(1) — in‑place.