30 lines concise c++ code with comments


  • 0
    Z
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if (!head) return head;
            if (!head->next) return head;
            ListNode* mid = head;   // find the middle node
            ListNode* fast = head;
            while (fast->next && fast->next->next) {
                mid = mid->next;
                fast = fast->next->next;
            }
            ListNode* right = sortList(mid->next); // sort right half list
            mid->next = NULL;   // segment list
            ListNode* left = sortList(head);    // sort left half list
            ListNode* ans = new ListNode(-1);
            ListNode* cur = ans;
            while (left || right) {     // merge two lists 
                if (!left || (right && right->val < left->val)) {
                    cur->next = right;
                    right = right->next;
                }
                else {
                    cur->next = left;
                    left = left->next;
                }
                cur = cur->next;
            }
            return ans->next;
        }
    };
    

  • 0
    W

    Thanks for you code. It really inspired me!


Log in to reply
 

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