凌云的博客

LeetCode 算法题 23. 合并K个排序链表

分类：algorithm| 发布时间：2016-07-08 10:51:00

---

题目

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解法 1：直观方法

这种方法比较的思想是将 2..k 个链表与第一个合并，由于每合并一次第一个链表的长度都会增加。 假设有 k 个链表，每个链表的长度为 n，则此算法的复杂度为 0(k^2 * n)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return NULL;
        }

        ListNode dummy(INT_MIN);
        dummy.next = lists[0];
        ListNode *p = &dummy, *tmp, *prev;
        for (int i = 1; i < lists.size(); ++i) {
            prev = &dummy;
            p = prev->next;
            ListNode *q = lists[i];
            while (p && q) {
                if (p->val <= q->val) {
                    prev = p;
                    p = p->next;
                } else {
                    tmp = q->next;
                    prev->next = q;
                    q->next = p;
                    prev = q;
                    q = tmp;
                }
            }

            if (!p) {
                prev->next = q;
            }
        }

        return dummy.next;
    }
};

解法 2：使用优先队列（堆）

将 k 个链表插入优先队列然后逐一取出就是需要的结果。 由于输入的 k 个链表本身是有序的，因此只需要将链表的地一个节点放入优先队列， 每次从优先队列取出节点后，检查 next 是否为 NULL，如果不为 NULL 则将 next 重新加入优先队列。 复杂度为 O(n * logk)。

class Solution {
    struct compare {
        bool operator()(const ListNode* l, const ListNode* r) {
            return l->val > r->val;
        }
    };

public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *, vector<ListNode *>, compare> q;
        for (auto l : lists) {
            if (l) {
                q.push(l);
            }
        }

        if (q.empty()) {
            return NULL;
        }

        ListNode* result = q.top();
        q.pop();
        if (result->next) {
            q.push(result->next);
        }

        ListNode* tail = result;
        while (!q.empty()) {
            tail->next = q.top();
            q.pop();
            tail = tail->next;
            if (tail->next) {
                q.push(tail->next);
            }
        }

        return result;
    }
};

解法 3：归并排序

归并排序非常适合合并多个有序队列，其复杂度为 O(n * logk)。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return partition(lists, 0, lists.size()-1);
    }

    ListNode* partition(vector<ListNode*>& lists, int start, int end){
        if (start == end) {
            return lists[start];
        }

        if (start < end) {
            int mid = (end+start)/2;
            ListNode* l1 = partition(lists, start, mid);
            ListNode* l2 = partition(lists, mid+1, end);
            return merge(l1, l2);
        }

        return NULL;
    }

    ListNode* merge(ListNode* l1, ListNode* l2){
        ListNode dummy(INT_MIN);
        ListNode *tail = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }

            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

修改下可以将其变为非递归的：

class Solution
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        const size_t k = lists.size();
        if (k == 0) return NULL;
        if (k == 1) return lists[0];

        for(size_t i = 1; i < k; i = i * 2) {
            for(size_t j = 0; j < k - i; j = j + i * 2) {
                lists[j] = merge(lists[j], lists[i + j]);
            }
        }

        return lists[0];
    }

    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(INT_MIN);
        ListNode *tail = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }

            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};