Neat c++ solution, using fast/slow pointer and merge sort


  • 3
    I
    ListNode* merge(ListNode *head1, ListNode *head2) {
        ListNode dummy(0), *cur = &dummy;
        while (head1 && head2) {
            if (head1->val <= head2->val) {
                cur->next = head1;
                head1 = head1->next;
            } else {
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        cur->next = head1 ? head1 : head2;
        return dummy.next;
    }
    
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode *slow = head, *fast = head->next;
        while (true) {
            if (!fast->next || !fast->next->next) {
                fast = slow->next;    
                slow->next = NULL;    // sever the list
                break;
            } else {
                fast = fast->next->next;
                slow = slow->next;
            }
        }
        return merge(sortList(head), sortList(fast));
    }

Log in to reply
 

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