[leetcode_148]Sort List

单链表排序。
用快排，某组测试数组超时。郁闷。
后来发现某大牛自己写的快排也过不了该数据。于是照他的思路写了堆排序，但是空间复杂度就不是常数了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        map<int, vector<ListNode *>> map_nodes;
        map_nodes.clear();
        while(head != NULL) {
            if(map_nodes.find(head->val) == map_nodes.end()) {
                vector<ListNode *> item;
                item.clear();
                item.push_back(head);
                map_nodes.insert(pair<int, vector<ListNode *>>(head->val, item));
            } else {
                map<int, vector<ListNode *>>::iterator it = map_nodes.find(head->val);
                it->second.push_back(head);
            }
            head = head->next; 
        }
        map<int, vector<ListNode *>>::iterator it = map_nodes.begin();
        head = it->second[0];
        ListNode *tmp = head;
        for(int i = 1; i < it->second.size(); i++) {
            tmp->next = it->second[i];
            tmp = tmp->next;
        }
        for(; it != map_nodes.end(); it++) {
            tmp->next = it->second[0];
            tmp = tmp->next;
            for(int i = 1; i < it->second.size(); i++) {
                tmp->next = it->second[i];
                tmp = tmp->next;
            }
        }
        tmp->next = NULL;
        return head;
    }
};