Problem Description

You are given the head of a singly linked list where the nodes are sorted in non-decreasing order based on their absolute values. Your task is to rearrange the linked list so that it becomes sorted in non-decreasing order based on the actual values of the nodes.

For example, if you have a linked list with values [-5, -3, 1, 4, 6] (sorted by absolute values: |−5|=5, |−3|=3, |1|=1, |4|=4, |6|=6 which gives us 1, 3, 4, 5, 6), you need to rearrange it to [-5, -3, 1, 4, 6] which is sorted by actual values.

The key insight is that when a list is sorted by absolute values, all negative numbers appear in reverse order compared to how they should appear when sorted by actual values. The solution leverages this property by moving negative nodes to the front of the list using head insertion. Starting from the second node, whenever a negative value is encountered, it's removed from its current position and inserted at the beginning of the list. Non-negative values remain in their current positions since they're already correctly ordered relative to each other.

The algorithm maintains two pointers: prev (the node before the current one) and curr (the current node being examined). When curr.val < 0, the node is extracted from its position and moved to become the new head. When curr.val >= 0, the traversal simply continues to the next node.

Intuition

When a linked list is sorted by absolute values, an interesting pattern emerges. Consider the values [-5, -3, -1, 2, 4, 6]. When sorted by absolute values, they become [-1, 2, -3, 4, -5, 6]. Notice that all positive numbers maintain their relative order and are already in the correct positions for the final sorted list. However, the negative numbers appear in reverse order compared to where they should be.

This observation is key: in a list sorted by absolute values, negative numbers with larger absolute values come later in the list, but in a list sorted by actual values, they should come first. For instance, -5 has the largest absolute value among negatives, so it appears last among the negative numbers when sorted by absolute value, but it should be first when sorted by actual value.

The breakthrough comes from realizing we can fix this in a single pass. As we traverse the list from left to right, every negative number we encounter needs to be moved to the front of the list, and more specifically, it needs to be placed before all previously encountered negative numbers. This is exactly what head insertion accomplishes - each newly found negative number becomes the new head, naturally creating the correct ordering.

Why does this work? Because we're processing negative numbers from smallest absolute value to largest absolute value (due to the original sorting), and inserting each at the head means the final order will be from largest absolute value to smallest - which corresponds to smallest actual value to largest for negative numbers. Meanwhile, positive numbers stay in place since they're already correctly ordered, resulting in a fully sorted list by actual values.

Learn more about Linked List, Two Pointers and Sorting patterns.

Solution Approach

The implementation uses the head insertion method with two pointers to rearrange the linked list in a single pass.

We start by initializing two pointers:

• prev points to the first node (initially head)
• curr points to the second node (initially head.next)

The algorithm then iterates through the list starting from the second node. For each node, we check if its value is negative:

When curr.val < 0 (negative value found):

1. Store the next node in a temporary variable t = curr.next
2. Disconnect the current node by setting prev.next = t
3. Insert the current node at the beginning by setting curr.next = head
4. Update the head pointer to the current node with head = curr
5. Continue traversal from the stored next node with curr = t

When curr.val >= 0 (non-negative value):

1. Simply move both pointers forward: prev = curr and curr = curr.next
2. The node remains in its current position

The key insight is that prev doesn't move forward when we extract a negative node - it stays pointing to the same node because we've removed the node between prev and the next node. This ensures we don't skip any nodes during traversal.

For example, with input [0, 2, -1, 4, -3]:

• Start: prev at 0, curr at 2 (positive, move forward)
• Next: prev at 2, curr at -1 (negative, extract -1 and insert at head)
• List becomes [-1, 0, 2, 4, -3], prev stays at 2, curr moves to 4
• Next: prev at 2, curr at 4 (positive, move forward)
• Next: prev at 4, curr at -3 (negative, extract -3 and insert at head)
• Final list: [-3, -1, 0, 2, 4]

The algorithm completes in O(n) time with O(1) extra space, making it an efficient solution.

Example Walkthrough

Let's walk through the algorithm with a concrete example to see how it transforms a list sorted by absolute values into one sorted by actual values.

Input: [1, -2, 3, -4, 5] (sorted by absolute values: |1|=1, |-2|=2, |3|=3, |-4|=4, |5|=5)

Initial Setup:

• head points to node with value 1
• prev points to node with value 1
• curr points to node with value -2

Step 1: Process node with value -2

• Since -2 < 0, we need to move it to the front
• Store next node (3) in temporary variable t
• Disconnect -2 by setting prev.next = t (1 now points to 3)
• Insert -2 at head: -2 → 1 → 3 → -4 → 5
• Update head to point to -2
• Keep prev at 1, move curr to 3

Step 2: Process node with value 3

• Since 3 ≥ 0, keep it in place
• Move prev to 3, move curr to -4
• List remains: -2 → 1 → 3 → -4 → 5

Step 3: Process node with value -4

• Since -4 < 0, we need to move it to the front
• Store next node (5) in temporary variable t
• Disconnect -4 by setting prev.next = t (3 now points to 5)
• Insert -4 at head: -4 → -2 → 1 → 3 → 5
• Update head to point to -4
• Keep prev at 3, move curr to 5

Step 4: Process node with value 5

• Since 5 ≥ 0, keep it in place
• Move prev to 5, move curr to null
• List remains: -4 → -2 → 1 → 3 → 5

Final Result: [-4, -2, 1, 3, 5] - correctly sorted by actual values!

Notice how negative numbers (-2 and -4) were moved to the front in reverse order of when we encountered them, which naturally sorts them correctly. The positive numbers (1, 3, 5) stayed in their original relative positions since they were already correctly ordered.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list.

The algorithm traverses the linked list exactly once using a single while loop. In each iteration, it performs constant-time operations:

• Checking if curr.val < 0 takes O(1)
• Pointer manipulations (prev.next = t, curr.next = head, etc.) take O(1)
• Moving to the next node takes O(1)

Since we visit each node exactly once and perform O(1) operations per node, the total time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a fixed number of variables regardless of the input size:

• prev: pointer to track the previous node
• curr: pointer to track the current node
• t: temporary pointer used during rearrangement

No additional data structures (arrays, stacks, recursion) are used that would grow with the input size. All operations are performed in-place by manipulating the existing linked list pointers. Therefore, the space complexity is constant, O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Handle Edge Cases

Issue: Not checking for empty lists or single-node lists can cause null pointer exceptions when trying to access head.next.

Incorrect Code:

def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev = head
    curr = head.next  # This fails if head is None!
    # ... rest of the code

Solution: Always validate input before processing:

if not head or not head.next:
    return head

Pitfall 2: Incorrectly Updating the prev Pointer

Issue: A common mistake is advancing prev after extracting a negative node, which causes nodes to be skipped.

Incorrect Code:

if curr.val < 0:
    temp_next = curr.next
    prev.next = temp_next
    curr.next = head
    head = curr
    prev = prev.next  # WRONG! This skips checking the next node
    curr = temp_next

Solution: Keep prev pointing to the same node after extraction since the next node now directly follows prev:

if curr.val < 0:
    temp_next = curr.next
    prev.next = temp_next
    curr.next = head
    head = curr
    # Don't move prev!
    curr = temp_next

Pitfall 3: Losing Track of the Next Node

Issue: Failing to store curr.next before modifying pointers results in losing the rest of the list.

Incorrect Code:

if curr.val < 0:
    prev.next = curr.next  # curr.next is about to be modified!
    curr.next = head       # Now the original curr.next is lost
    head = curr
    curr = ???  # We don't have access to the original next node anymore

Solution: Always store the next node in a temporary variable first:

if curr.val < 0:
    temp_next = curr.next  # Store it first!
    prev.next = temp_next
    curr.next = head
    head = curr
    curr = temp_next

Pitfall 4: Not Updating the Head Reference

Issue: Forgetting to update the head reference after inserting a node at the beginning means the newly inserted nodes won't be part of the returned list.

Incorrect Code:

if curr.val < 0:
    temp_next = curr.next
    prev.next = temp_next
    curr.next = head
    # Forgot to update head = curr
    curr = temp_next

Solution: Always update the head pointer after insertion:

if curr.val < 0:
    temp_next = curr.next
    prev.next = temp_next
    curr.next = head
    head = curr  # Critical: update the head!
    curr = temp_next