首页 > 代码库 > leetcode Insertion Sort List

leetcode Insertion Sort List

利用插入排序,对链表进行排序。

插入排序点here。

居然初次想用unordered map来存每个节点,然后根据下标就可以访问了,再更新下班,也就是n方的方法了。但是不知为什么超时了。插入排序不就是n方吗。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *insertionSortList(ListNode *head)     {        if (!head || !head -> next) return head;                unordered_map<int, ListNode *> umap;        ListNode *tmp = head;        int cnt = 0;        while(tmp)        {            umap[cnt++] = tmp;            tmp = tmp -> next;        }        ListNode *pre = new ListNode(0);        pre -> next = head;        umap[-1] = pre;        for (int i = 1; i < cnt; i++)        {            tmp = umap[i];            bool flag = false;            int j = i - 1;            while(j >= 0 && umap[i] -> val < umap[j] -> val)            {                j--;                flag = true;            }                        if (flag)            {// 处理umap的下标                for (int k = i - 1; k > j; k--)                    umap[k+1] = umap[k];                umap[j+1] = tmp;                // 处理指针指向                umap[i] -> next = umap[j+1] -> next;                umap[j+1] -> next = umap[j] -> next;                umap[j] -> next = umap[j+1];            }        }        head = pre -> next;        delete pre;        return head;    }};
View Code

 

然后就不从后往前插入,而是从前往后判断,复杂度应该是一样的,只是不要用到map,避免了更新map下标的操作。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *insertionSortList(ListNode *head)     {        if (!head || !head -> next) return head;                ListNode *pre = new ListNode(0);        pre -> next = head;        ListNode *p = head->next, *prep = head, *start = head, *preStart = pre;                while(p)        {            // 每次从头往后找第一个比p大的            preStart = pre;            start = preStart -> next;// 注意了每次的开始不是head,因为head可能已经变了,开始应该是pre的next            while(start != p && start->val <= p->val)            {                preStart = preStart -> next;                start = start->next;            }            if (start == p)            {                prep = p;                p = p -> next;            }            else            {                prep -> next = p -> next;                p -> next = start;                preStart -> next = p;                p = prep -> next; // 继续下一次的时候是prep的下一个了,也就是之前p的下一个            }        }            head = pre -> next;        delete pre;        return head;    }};

 

leetcode Insertion Sort List