60ms C++ solution,avoid memory leaks


  • 0
    H
    // merge
    ListNode* merge(ListNode *head1, ListNode* head2) {
    	ListNode *fake = new ListNode(0);
    	ListNode *cur = fake;
    	while (head1 || head2)
    	{
    		if (head1 && (!head2 || head1->val <= head2->val)) {
    			cur = cur->next = head1;
    			head1 = head1->next;
    		}
    		if (head2 && (!head1 || head2->val < head1->val)) {
    			cur = cur->next = head2;
    			head2 = head2->next;
    		}
    	}
    	ListNode *head = fake->next;
    	delete fake;
    	return head;
    }
    ListNode* LinkList::sortList(ListNode* head) {
    	if (!head || !head->next) return head;
    	ListNode *slow = head, *fast = head->next;
    	while (fast && fast->next) { // to find middle node
    		fast = fast->next->next;
    		slow = slow->next;
    	}
    	ListNode *head2 = slow->next; // head2 is the start of 2nd half of the list
    	slow->next = NULL; // split! now head is the start of 1st half of the list
    	return merge(sortList(head), sortList(head2));
    }

Log in to reply
 

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