LeetCode 2046 - Sort Linked List Already Sorted Using Absolute Values

The problem provides a singly linked list where the nodes are sorted in non-decreasing order by their absolute values, rather than their actual values. The task is to rearrange this list so that the nodes are sorted in non-decreasing order according to their actual values.

leetcodemediumlinked-listtwo-pointerssorting

LeetCode Problem 2046

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers, Sorting

Solution

Problem Understanding

The problem provides a singly linked list where the nodes are sorted in non-decreasing order by their absolute values, rather than their actual values. The task is to rearrange this list so that the nodes are sorted in non-decreasing order according to their actual values.

For example, consider the input [0, 2, -5, 5, 10, -10]. While the absolute values [0, 2, 5, 5, 10, 10] are sorted, the negative numbers are out of order when considering their true values. The output should be [-10, -5, 0, 2, 5, 10].

The input is a singly linked list, not an array. The constraints are substantial: the list may contain up to 100,000 nodes with values in the range [-5000, 5000]. This means that a naive approach that converts the list to an array and sorts it would be too slow if it relies on comparison-based sorting that uses extra memory.

Important edge cases include:

  1. A list containing only non-negative numbers, which is already sorted by actual value.
  2. A list containing only negative numbers, which will require reversing the negative segment.
  3. A single-node list, which is trivially sorted.
  4. Lists with zeros and duplicates, which should maintain proper order.

The problem also hints at a linear time solution, which suggests that a clever use of the linked list properties is possible without full sorting.

Approaches

The brute-force approach involves traversing the linked list, extracting all values into an array, sorting the array using a standard comparison sort, and then reconstructing the linked list. While this works correctly, it is not optimal for large lists because it uses extra memory for the array and incurs O(n log n) time complexity.

The optimal approach leverages the observation that the list is already sorted by absolute values. This guarantees that all negative numbers (in absolute value order) appear before their positive counterparts. If we reverse the negative sublist and then merge it with the positive sublist, we can achieve a fully sorted linked list in O(n) time and O(1) extra space. The steps involve splitting the list at the first non-negative node, reversing the negative sublist, and performing a standard merge of two sorted lists.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Convert list to array, sort, reconstruct linked list
Optimal O(n) O(1) Reverse negative sublist and merge with positive sublist in-place

Algorithm Walkthrough

  1. Identify the negative sublist: Start from the head and move forward while the nodes have negative values. Stop at the first non-negative node. This splits the list into a negative sublist and a non-negative sublist.
  2. Reverse the negative sublist: Since the negative numbers are in decreasing absolute order, reversing this sublist will order them correctly by actual value.
  3. Merge the two sorted sublists: Use a standard two-pointer merge technique for linked lists. Initialize a dummy head and compare nodes from both sublists, appending the smaller node each time.
  4. Return the merged list: After the merge, the dummy head points to the fully sorted linked list by actual values.

Why it works: Negative numbers in the input list are sorted by absolute value but decreasing in actual value. Reversing them ensures ascending order. Positive numbers are already sorted. Merging two sorted lists guarantees a fully sorted result. This preserves linear time complexity and constant extra space.

Python Solution

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # Step 1: Split the negative and non-negative lists
        neg_dummy = ListNode(0)
        pos_dummy = ListNode(0)
        neg_tail, pos_tail = neg_dummy, pos_dummy
        curr = head

        while curr:
            next_node = curr.next
            curr.next = None
            if curr.val < 0:
                curr.next = neg_dummy.next
                neg_dummy.next = curr
            else:
                pos_tail.next = curr
                pos_tail = pos_tail.next
            curr = next_node

        # Step 2: Merge the two lists
        neg_head = neg_dummy.next
        pos_head = pos_dummy.next
        dummy = ListNode(0)
        tail = dummy

        while neg_head and pos_head:
            if neg_head.val < pos_head.val:
                tail.next = neg_head
                neg_head = neg_head.next
            else:
                tail.next = pos_head
                pos_head = pos_head.next
            tail = tail.next

        tail.next = neg_head if neg_head else pos_head
        return dummy.next

The implementation first splits the input list into negative and non-negative segments. The negative nodes are prepended during traversal to reverse them in-place. Finally, a standard merge merges the reversed negative list with the positive list.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortLinkedList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    var negHead *ListNode
    dummyPos := &ListNode{}
    posTail := dummyPos
    curr := head

    for curr != nil {
        next := curr.Next
        curr.Next = nil
        if curr.Val < 0 {
            curr.Next = negHead
            negHead = curr
        } else {
            posTail.Next = curr
            posTail = posTail.Next
        }
        curr = next
    }

    dummy := &ListNode{}
    tail := dummy
    for negHead != nil && dummyPos.Next != nil {
        if negHead.Val < dummyPos.Next.Val {
            tail.Next = negHead
            negHead = negHead.Next
        } else {
            tail.Next = dummyPos.Next
            dummyPos.Next = dummyPos.Next.Next
        }
        tail = tail.Next
    }

    if negHead != nil {
        tail.Next = negHead
    } else if dummyPos.Next != nil {
        tail.Next = dummyPos.Next
    }

    return dummy.Next
}

The Go version mirrors the Python solution. Pointers are carefully updated, and nil is used instead of Python’s None. Negative nodes are reversed inline by prepending, while positive nodes maintain their order. The merge uses two pointers similar to the Python version.

Worked Examples

Example 1: [0, 2, -5, 5, 10, -10]

Step 1: Split

  • Negative list: -5 -> -10 (prepended → -10 -> -5)
  • Positive list: 0 -> 2 -> 5 -> 10

Step 2: Merge

Neg Pos Merged
-10 0 -10
-5 0 -10 -> -5
nil 0 -10 -> -5 -> 0 -> 2 -> 5 -> 10

Output: [-10, -5, 0, 2, 5, 10]

Example 2: [0, 1, 2]

Negative list: empty

Positive list: 0 -> 1 -> 2

Merge result: 0 -> 1 -> 2

Example 3: [1]

Only one node, returned as is: [1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited once for splitting, once for merging
Space O(1) Reversing negative nodes and merging done in-place with no extra arrays

The linear time complexity arises because the list is traversed a constant number of times, and no nested loops are used. Constant space is maintained by using pointer manipulation rather than auxiliary data structures.

Test Cases

# Provided examples
assert Solution().sortLinkedList(None) == None  # Empty list
assert Solution().sortLinkedList(ListNode(1)).val == 1  # Single node
assert Solution().sortLinkedList(ListNode(0, ListNode(2, ListNode(-5, ListNode(5, ListNode(10, ListNode(-10))))))).val == -10

# Edge cases
assert Solution().sortLinkedList(ListNode(-3, ListNode(-2, ListNode(-1)))).val == -3  # All negative
assert Solution().sortLinkedList(ListNode(0, ListNode(0, ListNode(0)))).val == 0  # All zeros
assert Solution().sortLinkedList(ListNode(-1, ListNode(1))).val == -1  # Mixed one negative, one positive
Test Why
Empty list Validate handling of no nodes
Single node Validate trivial case
Mixed positive/negative Validates full algorithm
All negative