148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

S: merge sort O(nlogn)

    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode *l1, *l2;
        l2 = breakList(head);
        l1 = sortList(head);
        l2 = sortList(l2);
        return mergeList(l1, l2);
    }

    ListNode* breakList(ListNode* head) {
        ListNode *fast = head, *slow = head, *tail;
        while(fast && fast->next) {
            fast = fast->next->next;
            tail = slow;
            slow = slow->next;
        }
        tail->next = NULL;
        return slow;
    }

    ListNode* mergeList(ListNode* head1, ListNode* head2) {
        ListNode dummy(0);
        ListNode *head = &dummy;
        while(head1 || head2) {
            if(!head2 || (head1 && (head1->val < head2->val))) {
                head->next = head1;
                head1 = head1->next;
            }
            else {
                head->next = head2;
                head2 = head2->next;
            }
            head = head->next;
        }
        return dummy.next;
    }

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

S: two pointer + dummy node O(n)

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* node = &dummy;
        while(l1 && l2) {
            if (l1->val <= l2->val) {
                node->next = l1;
                l1 = l1->next;
            } else {
                node->next = l2;
                l2 = l2->next;
            }
            node = node->next;
        }
        if (l1) node->next = l1;
        if (l2) node->next = l2;
        return dummy.next;
    }

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

S1: 两两merge

S2: priority_queue 最小优先序列

1. 用每个list的头指针构建priority_queue()。因为默认pq是最大堆，所以需要重新定义比较函数为最小堆

2. 每次取pq的top为当前节点并push top->next 进pq

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummy(-1);
        ListNode *cur = &dummy;
        priority_queue<ListNode*, vector<ListNode*>, myCompare> q;
        for(auto &i : lists){
            if(i) q.push(i);
        }
        while(!q.empty()){
            cur->next = q.top();
            q.pop();
            if(cur->next->next) q.push(cur->next->next);
            cur = cur->next;
        }
        return dummy.next;
    }
private:
    struct myCompare{
        bool operator()(ListNode *a, ListNode *b){
            return a->val > b->val;//priority_queue use less<T>, is a max heap, here we need min heap;
        }
    }; 
};

147. Insertion Sort List

Sort a linked list using insertion sort.

    ListNode* insertionSortList(ListNode* head) {
        if(!head) return NULL;
        ListNode dummy(0);
        while(head) {
            ListNode *nextNode = head->next;
            ListNode* before = &dummy;
            ListNode* cur = dummy.next;
            while(cur && cur->val <= head->val) {
                before = cur; 
                cur = cur->next;
            }
            before->next = head;
            head->next = cur;
            head = nextNode;
        }
        return dummy.next;
    }