Description

Submission

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    int bucket[10001];
    const int offset = 5000;
public:
    ListNode* sortLinkedList(ListNode* head) {
        for(ListNode *ptr = head; ptr != nullptr; ptr = ptr->next) {
            ++bucket[ptr->val+offset];
        }

        ListNode *ptr = head;
        for(int i = 0; i < 10001; ++i) {
            for(; bucket[i]; --bucket[i]) {
                ptr->val = i - offset;
                ptr = ptr->next;
            }
        }

        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortLinkedList(ListNode* head) {
        ListNode *dummy1 = new ListNode();
        ListNode *dummy2 = new ListNode();
        ListNode *ptr1 = dummy1, *ptr2 = dummy2;
        for(ListNode *ptr = head; ptr; ptr = ptr->next) {
            if(ptr->val < 0) ptr1 = ptr1->next = ptr;
            else ptr2 = ptr2->next = ptr;
        }
        ptr1->next = ptr2->next = nullptr;

        // reverse list 1
        ListNode *nextNode = nullptr, *tail = dummy1->next;
        for(ListNode *cur = dummy1->next; cur; ) {
            ListNode *curNext = cur->next;
            cur->next = nextNode;
            nextNode = cur;
            cur = curNext;
        }
        dummy1->next = nextNode;

        if(!dummy1->next) return dummy2->next;
        if(!dummy2->next) return dummy1->next;

        // merge
        tail->next = dummy2->next;
        
        return dummy1->next;
    }
};