Solution Explanation: Sorting a Linked List by Absolute Value then Actual Value

This problem requires sorting a singly linked list that's already sorted by the absolute values of its nodes, into a new list sorted by the actual values. The key insight is to leverage the fact that the list is already sorted by absolute values. This allows for an efficient solution that avoids a full-blown sorting algorithm like merge sort or quicksort.

Algorithm:

The most efficient approach is a variation of insertion sort. We iterate through the list, and whenever we encounter a negative number, we insert it into its correct position in the sorted portion of the list using head insertion. This is because inserting at the head is O(1) and we already know the list is sorted (by absolute values), so we can intelligently find the correct position.

1. Initialization: We maintain two pointers: prev (pointing to the node before the current node) and curr (pointing to the current node).
2. Iteration: We iterate through the linked list starting from the second node.
3. Negative Value Handling: If curr.val is negative, we perform a head insertion:
   • Store the next node of curr in a temporary variable t.
   • Update prev.next to skip over curr.
   • Set curr.next to head to insert curr at the beginning of the list.
   • Update head to curr.
   • Update curr to t.
4. Positive Value Handling: If curr.val is non-negative, we simply move prev and curr to the next nodes.
5. Return: After iterating through the entire list, we return the updated head.

Time Complexity: O(n) - We traverse the list once. The head insertion operation within the loop takes constant time.

Space Complexity: O(1) - We use only a constant number of extra variables.

Code Examples (Python):

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def sortLinkedList(self, head: ListNode) -> ListNode:
        if not head or not head.next:  # Handle empty or single-node lists
            return head
 
        prev, curr = head, head.next
        while curr:
            if curr.val < 0:
                temp = curr.next
                prev.next = temp
                curr.next = head
                head = curr
                curr = temp
            else:
                prev, curr = curr, curr.next
        return head
 

The Java, C++, Go, and TypeScript examples in the original response follow the same algorithm and have the same time and space complexity. They are simply different implementations of the same core logic. The essential elements (two pointers, conditional head insertion) remain consistent across all languages.