148. Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

• insertion sort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return head;
        ListNode* dummy = new ListNode(INT_MIN);
        ListNode* dummyTail = dummy;
        ListNode* cur = head;
        while(cur) {
            ListNode* newTail = cur->next;
            cur->next = NULL;
            if(cur->val > dummyTail->val) {
                dummyTail->next = cur;
                dummyTail = cur;
            } else {
                ListNode* tmp = dummy;
                while(tmp->next and tmp->next->val < cur->val)
                    tmp = tmp->next;
                cur->next = tmp->next;
                tmp->next = cur;
            }
            cur = newTail;
        }
        return dummy->next;
    }
};

• merge sort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* left) {
        if(!left or !(left->next)) return left;
        ListNode* right = left;
        ListNode* half = left;
        while(!right and !(right->next)) {
            half = half->next;
            right = right->next->next;
        }
        right = half->next;
        half->next = NULL;
        return merge(sortList(left), sortList(right));
    }
    
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode* dummy = new ListNode(INT_MIN);
        ListNode* tail = dummy;
        while(left and right) {
            if(left->val > right->val) {
                tail->next = right;
                right = right->next;
            } else {
                tail->next = left;
                left = left->next;
            }
            tail = tail->next;
        }
        tail->next = left ? left : right;

        return dummy->next;
    }
};