Three Methods to sort a Linked list.


  • 0
    B

    1: Insertion sort(24ms):

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            if(!head) return head;
            ListNode * dummy = new ListNode(0);
            dummy->next = head;
            ListNode* cur = head;
            
            while(cur && cur->next){
                if(cur->next->val < cur->val){
                    ListNode * pre = dummy;
                    ListNode * tmp = cur->next;
                    while(pre->next->val < tmp->val)
                        pre = pre->next;
                    cur->next = tmp->next;
                    tmp->next = pre->next;
                    pre->next = tmp;
                }else cur = cur->next;
            }
            head = dummy->next;
            delete dummy;
            return head;
        }
    };
    

    2: with array and sort(20ms):

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            vector<int> dump;
            ListNode * cur = head;
            while(cur){
                dump.push_back(cur->val);
                cur = cur->next;
            }
            sort(dump.begin(), dump.end());
            cur = head;
            for(auto iter=dump.begin(); iter!=dump.end(); ++iter, cur = cur->next){
                cur->val = *iter;
            }
            return head;
        }
    };
    

    3: merge sort(22ms):

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            return mergeSort(head);
        }
        ListNode * mergeSort(ListNode* head){
            if(!head || !head->next) return head;
            ListNode * fast = head, * slow = head;
            while(slow->next && fast->next && fast->next->next){//fast->next->next might cause runtime error without fast->next.
                fast = fast->next->next;
                slow = slow->next;
            }
            ListNode * leftHead = head;
            ListNode * rightHead = slow->next;
            slow->next = nullptr;
            leftHead = mergeSort(leftHead);
            rightHead = mergeSort(rightHead);
            return mergeList(leftHead, rightHead);
        }
        ListNode* mergeList(ListNode * lhead, ListNode * rhead){
            ListNode dummy(0), *p1 = &dummy, *p2 = rhead;
            p1->next = lhead;
            while(p1->next && p2){
                if(p1->next->val> p2->val){//keep stable
                    ListNode * tmp = p2;
                    p2 = p2->next;
                    tmp->next = p1->next;
                    p1 ->next = tmp;
                    p1 = p1->next;
                }else{
                    p1 = p1->next;
                }
            }
            if(p2) p1->next = p2;
            return dummy.next;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.