C++ 58ms solution, partition and merge


  • 0
    class Solution {
    public:
    
    ListNode* mergeList(ListNode* h1, ListNode* h2){
        if (h1==NULL) return h2;
        if (h2==NULL) return h1;
        ListNode *head,*cur;
        if (h1->val<h2->val){
            head = h1;h1=h1->next;cur=head;
        }else{
            head = h2;h2=h2->next;cur=head;
        }
        while(h1&&h2){
            if (h1->val<h2->val){
                cur->next = h1;
                h1 = h1->next;
            }
            else{
                cur->next = h2;
                h2 = h2->next;
            }
            cur = cur->next;
        }
        if (h1) cur->next = h1;
        if (h2) cur->next = h2;
        return head;
    }
    ListNode* sortList(ListNode* head) {
        if (head==NULL ||head->next==NULL) return head;
        ListNode *fast=head,*slow=head;
        while(fast->next!=NULL && fast->next->next!=NULL){
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = slow->next;
        slow->next = NULL;
        return mergeList(sortList(head),sortList(fast));
    }
    };

Log in to reply
 

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