148-sort-list.cpp

/**
 * 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* sortList(ListNode* head) {
        vector<ListNode*> values;
        if (!head) return head;
        if (!head->next) return head;
        // Move to vector
        while(head) {
            values.push_back(head);
            head = head->next;
        }
        // sort by val
        sort(values.begin(),values.end(),[](ListNode* a, ListNode* b) {
            return a->val < b->val;
        });
        // fix pointers
        ListNode* prev = nullptr;
        for (ListNode* curr : values) {
            if (prev) {
                prev->next = curr;
            }
            prev = curr;
        }
        prev->next = nullptr;

        return values.at(0);

/*      ListNode* pivot = head;
        ListNode* left = new ListNode();
        ListNode* right = new ListNode();
        ListNode* leftT = left;
        ListNode* rightT = right;

        if (pivot == NULL)
            return pivot;
        ListNode* curr = pivot->next;
        while (curr) {
            // Coloco
            if (pivot->val >= curr->val) {
                leftT->next = curr;
                leftT = curr;
            }
            // Coloco
            if (pivot->val < curr->val) {
                rightT->next = curr;
                rightT = curr;
            }
            // Avanzo
            curr = curr->next;
        }
        leftT->next = nullptr;
        rightT->next = nullptr;

        left = sortList(left->next);
        right = sortList(right->next);
        
        if (left) {
            leftT = left;
            while(leftT->next) leftT = leftT->next;
            leftT->next = pivot;
        } else {
            left = pivot;
        }
       
        pivot->next = right;
        return left;*/
    }
};