LeetCode Solutions Blog

Sort Linked List Already Sorted Using Absolute Values

Number: 1992

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given the head of a singly linked list that is sorted in non-decreasing order based on the absolute values of its nodes, return the list sorted in non-decreasing order according to the actual values of its nodes.

Key Insights

The original list is ordered by the absolute value, which means negative values may be in reverse order relative to their actual value.
The list can essentially be split into two sorted parts: one with negative numbers (in descending order) and one with non-negative numbers (in ascending order).
Reverse the negative part to obtain its correct ascending order, and then merge the two sorted sub-lists using a two-pointer technique.
The merging process is analogous to merging two sorted arrays.

Space and Time Complexity

Time Complexity: O(n) – each node is processed a constant number of times. Space Complexity: O(1) – no additional data structures are used aside from pointers.

Solution

We approach the problem by first partitioning the list into two parts:

The negative sub-list (which is in descending order with respect to actual values).
The non-negative sub-list (which is already in ascending order).

Next, we reverse the negative sub-list so that it becomes sorted in non-decreasing order. Finally, we merge the two sorted sub-lists into one fully sorted list. This merging can be efficiently done using the two-pointer technique, similar to the merge step in merge sort.

The key trick is to leverage the properties of the input list: knowing that the list is already “almost sorted” by absolute value allows us to complete the task in linear time without having to perform a full sort from scratch.

Code Solutions

# 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:
        # Dummy heads for negative and non-negative lists
        negative_dummy = ListNode(0)
        non_negative_dummy = ListNode(0)
        
        neg_ptr = negative_dummy
        non_neg_ptr = non_negative_dummy
        
        # Separate the list into negative and non-negative parts.
        current = head
        while current:
            if current.val < 0:
                neg_ptr.next = current
                neg_ptr = neg_ptr.next
            else:
                non_neg_ptr.next = current
                non_neg_ptr = non_neg_ptr.next
            current = current.next
        
        # End the non_negative list.
        non_neg_ptr.next = None
        # End the negative list.
        neg_ptr.next = None

        # Reverse the negative list.
        prev = None
        current = negative_dummy.next
        while current:
            next_temp = current.next
            current.next = prev
            prev = current
            current = next_temp
        reversed_negative = prev

        # Merge the two sorted lists (reversed_negative and non_negative_dummy.next).
        dummy = ListNode(0)
        tail = dummy
        ptr1 = reversed_negative
        ptr2 = non_negative_dummy.next
        
        while ptr1 and ptr2:
            if ptr1.val <= ptr2.val:
                tail.next = ptr1
                ptr1 = ptr1.next
            else:
                tail.next = ptr2
                ptr2 = ptr2.next
            tail = tail.next
        
        # Append any remaining nodes.
        tail.next = ptr1 if ptr1 else ptr2
        
        return dummy.next

# Example usage:
# This would be the method for testing the solution with a custom linked list build.