147. Insertion Sort List

Total Accepted: 92484
Total Submissions: 288998
Difficulty: Medium
Contributors: Admin

Sort a linked list using insertion sort.

分析

按照传统的插入方法，对list进行排序 56ms

/**
 * 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) {
        ListNode * curi = head, * curj = head;
        ListNode dummy(INT_MIN);
        dummy.next = NULL;
        while(curi != NULL){
            curj = &dummy;
            ListNode * node = curi;
            curi = curi->next;
            while(curj != NULL){
                if(curj->next == NULL || curj->val<= node->val && curj->next->val > node->val){
                    ListNode * tmp = curj->next;
                    curj->next = node;
                    node->next = tmp;
                    break;
                }
                curj = curj->next;
            }
        }
        return dummy.next;
    }
};

将list的数值，赋值倒vector<int>中，然后排序结束，再依次赋值回去 19ms

/**
 * 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 == NULL) return head;
        vector<int> list;
        ListNode * h = head;
        while(h != NULL){
            list.push_back(h->val);
            h = h->next;
        }
        sort(list.begin(), list.end());
         
        h = head;
        for(auto val: list){
            h->val = val;
            h = h->next;
        }
        return head;
    }
};

null