https://leetcode.com/problems/sort-list/

1. Using STL:

  1. //76 ms, 14.1 MB
  3. /**
  4.  * Definition for singly-linked list.
  5.  * struct ListNode {
  6.  *     int val;
  7.  *     ListNode *next;
  8.  *     ListNode(int x) : val(x), next(NULL) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* sortList(ListNode* head) {
  14.         if(!head) return nullptr;
  16.         vector<int> treelist;
  18.         ListNode* curr = head;
  20.         while(head){
  21.             treelist.push_back(head->val);
  22.             head = head->next;
  23.         }
  25.         sort(treelist.begin(), treelist.end());
  27.         ListNode* dummy = new ListNode(INT_MIN);
  28.         ListNode* newhead = dummy;
  30.         for(int i=0; i<treelist.size(); i++){
  31.             newhead->next = new ListNode(treelist[i]);
  32.             newhead = newhead->next;
  33.         }
  35.         return dummy->next;
  36.     }
  37. };

2. Using swap sort:

//1860 ms, 15.7 MB

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return nullptr;

        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* first = dummy->next;
        ListNode* second = dummy->next->next;
        ListNode* prev = dummy->next;

        while(second){
            if(second->val < first->val){
                if(prev == first){
                    dummy->next = second;
                    prev->next = second->next;
                    second->next = prev;

                    second = first->next;
                    first = dummy->next;
                } else {
                    ListNode* tmp = first->next;

                    dummy->next = second;                                  
                    first->next = second->next;
                    second->next = tmp;
                    prev->next = first;          

                    second = first->next;
                    first = dummy->next;
                    prev = prev->next;
                }
            } else {
                prev = prev->next;
                second = second->next;
            }
        }

        /*
        ListNode* test = dummy->next;
        while(test){
            cout << test->val << "->";
            test = test->next;
        }
        cout << "NULL" << endl;
        */

        first->next = sortList(dummy->next->next);

        return first;
    }
};

3. Use merge sort: