Formatted question description: https://leetcode.ca/all/2046.html

2046. Sort Linked List Already Sorted Using Absolute Values (Medium)

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

 

Example 1:

Input: head = [0,2,-5,5,10,-10]
Output: [-10,-5,0,2,5,10]
Explanation:
The list sorted in non-descending order using the absolute values of the nodes is [0,2,-5,5,10,-10].
The list sorted in non-descending order using the actual values is [-10,-5,0,2,5,10].

Example 2:

Input: head = [0,1,2]
Output: [0,1,2]
Explanation:
The linked list is already sorted in non-decreasing order.

Example 3:

Input: head = [1]
Output: [1]
Explanation:
The linked list is already sorted in non-decreasing order.

 

Constraints:

• The number of nodes in the list is the range [1, 105].
• -5000 <= Node.val <= 5000
• head is sorted in non-decreasing order using the absolute value of its nodes.

 

Follow up:

• Can you think of a solution with O(n) time complexity?

Related Topics:
Linked List, Two Pointers, Sorting

Similar Questions:

• Sort List (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/sort-linked-list-already-sorted-using-absolute-values/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* sortLinkedList(ListNode* head) {
        ListNode dummy;
        dummy.next = head;
        while (head->next) {
            auto node = head->next;
            if (node->val >= 0) {
                head = head->next;
            } else {
                head->next = node->next;
                node->next = dummy.next;
                dummy.next = node;
            }
        }
        return dummy.next;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/sort-linked-list-already-sorted-using-absolute-values/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* sortLinkedList(ListNode* head) {
        ListNode pos, *posTail = &pos, neg, *negTail = NULL;
        while (head) {
            auto node = head;
            head = head->next;
            if (node->val >= 0) {
                posTail->next = node;
                posTail = node;
            } else {
                node->next = neg.next;
                neg.next = node;
                if (!negTail) negTail = node;
            }
        }
        if (negTail) {
            negTail->next = pos.next;
            posTail->next = NULL;
            return neg.next;
        }
        return pos.next;
    }
};

All Problems

All Solutions