Code Implementation

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:
            return head

        # Dummy head for the result list
        dummy = ListNode(0)
        dummy.next = head

        prev = dummy
        curr = head

        while curr and curr.next:
            # If next node is negative, move it to the front
            if curr.next.val < 0:
                temp = curr.next
                curr.next = temp.next
                # Insert temp after dummy
                temp.next = dummy.next
                dummy.next = temp
            else:
                curr = curr.next
        return dummy.next
      

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* sortLinkedList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        ListNode* curr = head;

        while (curr && curr->next) {
            if (curr->next->val < 0) {
                ListNode* temp = curr->next;
                curr->next = temp->next;
                temp->next = dummy.next;
                dummy.next = temp;
            } else {
                curr = curr->next;
            }
        }
        return dummy.next;
    }
};
      

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode sortLinkedList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy, curr = head;
        while (curr != null && curr.next != null) {
            if (curr.next.val < 0) {
                ListNode temp = curr.next;
                curr.next = temp.next;
                temp.next = dummy.next;
                dummy.next = temp;
            } else {
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}
      

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

var sortLinkedList = function(head) {
    if (!head || !head.next) return head;
    let dummy = new ListNode(0, head);
    let curr = head;

    while (curr && curr.next) {
        if (curr.next.val < 0) {
            let temp = curr.next;
            curr.next = temp.next;
            temp.next = dummy.next;
            dummy.next = temp;
        } else {
            curr = curr.next;
        }
    }
    return dummy.next;
};
      

Problem Description

You are given the head of a singly linked list, head, where the list is already sorted in increasing order by the absolute value of each node's value. However, the actual values may be negative or positive.
Your task is to sort the linked list in increasing order by actual value (not by absolute value), and return the head of the sorted linked list.

• Each node in the list contains a unique integer value (no duplicates).
• You must not create new nodes; only rearrange the existing nodes.
• There is exactly one valid solution for each input.

For example, if the input linked list is 1 -2 -3 4 5 (sorted by absolute value: 1, 2, 3, 4, 5), the sorted list by value should be -3 -2 1 4 5.

Thought Process

At first glance, you might consider extracting all values, sorting them, and rebuilding the list. However, the problem restricts us to rearranging existing nodes, not creating new ones.

Since the list is sorted by absolute value, all negative numbers (if any) appear in reverse order, interleaved with positive numbers. For example, 1 -2 -3 4 5: the negatives (-2, -3) are in decreasing order of their value, but increasing order of their absolute value.

To sort by actual value, we need to move all negative numbers to the front, but in the correct increasing order. This requires us to reverse the sequence of negative numbers as we encounter them.

Instead of brute-forcing with O(n^2) insertion, we can exploit the property that all negatives are out of order and all positives are already in place. By traversing the list and moving each negative node to the front, we can achieve the desired order efficiently.

Solution Approach

The approach is based on a single pass through the linked list, rearranging nodes in-place:

1. Initialize a dummy node: Create a dummy node before the head to simplify edge cases, especially when moving nodes to the front.
2. Traverse the list: Use a pointer (curr) to iterate through the list. For each node, check if the next node's value is negative.
3. Move negative nodes: If curr.next is negative, detach it and insert it immediately after the dummy node (i.e., at the front of the list). This reverses the order of negative nodes as we find them, which is necessary because they are currently ordered by decreasing value.
4. Continue traversal: If the next node is not negative, simply move to the next node.
5. Return the sorted list: After processing all nodes, return dummy.next as the new head.

This process ensures all negative nodes are in correct order at the front, followed by all non-negative nodes, preserving their original order.

Example Walkthrough

Let's use the sample input: 1 -2 -3 4 5

1. Start with dummy -> 1 -2 -3 4 5
2. curr = 1. curr.next = -2 (negative). Move -2 to front:
   dummy -> -2 -> 1 -3 4 5
3. curr = 1 again. curr.next = -3 (negative). Move -3 to front:
   dummy -> -3 -> -2 -> 1 4 5
4. curr = 1. curr.next = 4 (not negative). Move curr to 4.
5. curr = 4. curr.next = 5 (not negative). Move curr to 5.
6. All nodes processed. Final list: -3 -2 1 4 5

Notice how each negative node is inserted at the front, reversing their order relative to their appearance in the original list.

Time and Space Complexity

• Brute-force approach: Extract all values, sort, and rebuild the list. This would be O(n log n) time and O(n) extra space, but is not allowed by the problem constraints.
• Optimized in-place approach: We traverse the list once, and for each negative node, perform constant-time pointer manipulation. Thus, the time complexity is O(n), where n is the number of nodes.
• No extra data structures are used; only a few pointers are maintained. Therefore, the space complexity is O(1) (in-place).

Summary

The key insight is that a list sorted by absolute value can be efficiently reordered by actual value through a single traversal: by moving each negative node to the front, we restore the correct increasing sequence. This leverages the original ordering and uses only pointer manipulations, making the solution both elegant and optimal.