合并两个有序链表

合并 K 个升序链表

合并两个有序链表

将两个有序的链表合成为一个有序链表

递归

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(!list1) return list2;
    if(!list2) return list1;

    if(list1->val < list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}

迭代

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(!list1) return list2;
    if(!list2) return list1;
    ListNode* head = new ListNode();
    ListNode* p = head;
    while(list1 && list2) {
        if(list1->val < list2->val) {
            p->next = list1;
            list1 = list1->next;
        }else {
            p->next = list2;
            list2 = list2->next;
        }
        p = p->next;
    }
    p->next = list1 ? list1 : list2;
    return head->next;
}

合并 K 个升序链表

堆排序

思路

此题可以采用堆排序的做法，第一步只将所有的头节点入堆，第二步一边获取最小值一边将next入堆。

因为是给定的升序链表，我们就可以保证当前堆中的m个元素一定是所有n个元素中的最小的一批。

代码

struct Heap{
    vector<ListNode*> h;
    Heap(){
        h.push_back(new ListNode(INT_MIN));
    }
    bool isEmpty() {
        return h.size() <= 1;
    }
    void offer(ListNode* x) {
        h.push_back(x);
        up(h.size() - 1);
    }
    ListNode* poll() {
        ListNode* res = h[1];
        h[1] = h.back();
        h.pop_back();
        down(1);
        return res;
    }
    void up(int x) {
        while(x / 2 && h[x / 2]->val > h[x]->val) {
            swap(h[x / 2], h[x]);
            x /= 2;
        }
    }
    void down(int x){
        int u = x;
        int l = x * 2;
        int r =  x * 2 + 1;
        int size = h.size() - 1;
        if(l <= size && h[l]->val < h[u]->val) u = l;
        if(r <= size && h[r]->val < h[u]->val) u = r;
        if(u != x) {
            swap(h[u], h[x]);
            down(u);
        }
    }
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
    Heap* heap = new Heap();
    for(auto head:lists) {
        if(head != nullptr) {
            heap->offer(head);   
        }
    }
    ListNode* head = new ListNode();
    ListNode* p = head;
    while(!heap->isEmpty()) {
        ListNode* x = heap->poll();
        p->next = x;
        p = p->next;
        if(x->next != nullptr) heap->offer(x->next);
    }
    return head->next;
}

分治

思路

可以将N个有序链表的合并转化为两个有序链表的合并。

代码

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.size() == 0) return nullptr;
    return merge(0, lists.size() - 1, lists);
}
ListNode* merge(int l, int r, vector<ListNode*>& lists) {
    if(l >= r) return lists[l];
    int mid = l + r >> 1;
    ListNode* leftLinkList = merge(l, mid, lists);
    ListNode* rightLinkList = merge(mid + 1, r, lists);
    return mergeTwoLists(leftLinkList, rightLinkList);
}
ListNode* mergeTwoLists(ListNode* p, ListNode* q) {
    if(p == nullptr) return q;
    if(q == nullptr) return p;
    ListNode* head = new ListNode();
    ListNode* cur = head;
    while(p && q) {
        if(p->val > q->val) {
            cur->next = q;
            q = q->next;
        }else {
            cur->next = p;
            p = p->next;
        }
        cur = cur->next;
    }
    cur->next = q ? q : p;
    return head->next;
}