合并K个已排序链表C语言,算法题解：合并k个已排序的链表

算法题解：合并k个已排序的链表

题目

为了简化分析，我们设共有k个链表，每个链表的最大长度为n。

题解1

不断取出值最小的那个Node(因为每个list已经排序，所以这一步只需要找出最小的head Node)，添加到已排序链表的尾部，直到所有lists的所有Node都取完。

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

*/

class Solution

{

ListNode *_mergeKLists(ListNode *head, ListNode *tail, vector &lists)

{

int smallest_node_index = find_smallest_head(lists);

// 结束递归的情况

if (smallest_node_index == -1)

{

tail->next = NULL;

return head;

}

tail->next = lists[smallest_node_index];

lists[smallest_node_index] = lists[smallest_node_index]->next;

// 尾递归

return _mergeKLists(head, tail->next, lists);

}

// 从所有链表中找到val最小的 headNode

int find_smallest_head(vector &lists)

{

int smallest_index = -1;

for (int i = 0; i < lists.size(); i++)

{

if (lists[i] == NULL)

{

lists.erase(lists.begin() + i);

// 删除第i项以后，下轮循环体还要访问第i项

i--;

continue;

}

if (smallest_index == -1 || lists[i]->val < lists[smallest_index]->val)

{

smallest_index = i;

}

}

return smallest_index;

}

public:

ListNode *mergeKLists(vector &lists)

{

// 通过 dummyHead ，避免对 “head== NULL && tail == NULL”情况进行额外判断处理

ListNode *dummyHead = new ListNode(-1);

ListNode *res = _mergeKLists(dummyHead, dummyHead, lists)->next;

delete dummyHead;

return res;

}

};

每一次递归调用_mergeKLists仅仅是将问题的规模减小1，而不是将问题分解为多个问题。因此，这可以被称为“减治法”，比“分治法”要慢一些。

这种解法虽然使用了尾递归，但是速度依然很慢。原因有2：

每次调用_mergeKLists的效果仅仅是解决了1个Node的顺序，对问题的简化程度太小，导致_mergeKLists需要调用O(nk)次。

每次调用_mergeKLists的时间开销较高。其时间复杂度为调用find_smallest_head的时间复杂度，o(k)，而且调用vector::erase的耗时较多。

综上所述，这种解法的时间复杂度为O(nk)*O(k)=O(nk^2)。实际耗时359 ms，仅仅超过9.73%的提交。不是一个好的算法。

题解2

分治思想：先将lists中的链表两两合并，然后问题就简化成了“合并k/2个已排序的链表”。

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

*/

class Solution

{

// 加入 merged_head 和 merged_tail 参数，是为了能够使用尾递归

ListNode *merge2Lists(ListNode *list1_head, ListNode *list2_head,

ListNode *merged_head, ListNode *merged_tail)

{

// 两种结束递归的情况

if (list1_head == NULL)

{

merged_tail->next = list2_head;

return merged_head;

}

else if (list2_head == NULL)

{

merged_tail->next = list1_head;

return merged_head;

}

// 需要继续递归的情况

else if (list1_head->val <= list2_head->val)

{

merged_tail->next = list1_head;

// 尾递归

return merge2Lists(list1_head->next, list2_head, merged_head, merged_tail->next);

}

else

{

merged_tail->next = list2_head;

// 尾递归

return merge2Lists(list1_head, list2_head->next, merged_head, merged_tail->next);

}

}

public:

ListNode *mergeKLists(vector &lists)

{

int lists_num = lists.size();

if (lists_num == 0)

return NULL;

ListNode *dummyHead = new ListNode(-1);

while (lists_num > 1)

{

for (int i = 0; i < lists_num / 2; i++)

{

// 通过 dummyHead ，避免对 “merged_head == NULL && merged_tail == NULL”情况进行额外判断处理

dummyHead->next = NULL;

lists[i] = merge2Lists(lists[i], lists[lists_num - 1 - i], dummyHead, dummyHead)->next;

}

// “简化问题”的过程，就是不断减半lists_num的过程

lists_num = (lists_num + 1) / 2;

}

delete dummyHead;

// 经过log_2(k)次减半，lists 中只剩下一个sortedList

return lists[0];

}

};

每执行一次while的循环体，需要合并的链表数就减半，因此while循环体执行次数为logk。

每次执行循环体的时间开销：第一次执行循环体：k/2次合并2个长度为n的链表，时间复杂度为O(nk)；第二次执行循环体：k/4次合并2个长度为2n的链表，时间复杂度依然为O(nk)。以此类推，每次执行循环体的时间开销都为O(nk)。

综上所述，此解法的时间复杂度为O(nklogk)。实际耗时26 ms，超过80.34%的提交。相比前面一个解法有巨大提升。

为什么题解2更加高效？

在题解1中，find_smallest_head的时间复杂度等于每次要合并的链表数(k)，而链表数在题解1的算法执行过程中是基本不变的。因此这个函数的执行时间始终很高，而调用一次这个函数仅仅能帮助我们选出一个最小的节点(每次选择的代价高，收益低)。算法的大部分时间都花在这个函数上了。

而题解2将【合并k个链表】分成k/2个独立的子问题：合并2个链表。独立的意义是：当我在合并2个链表的时候，完全不需要管其他的链表。这种独立性使得子问题能够非常高效的解决：每次只需要对比2个节点，就能选出一个节点。虽然每次选出的节点“质量比较差”(这个节点不太可能是k个链表中最小的那个节点，它仅仅是2个链表中最小的那个节点)，但是它胜在选择的成本非常低(仅仅执行一次大小比较)。因此每次的选择收益相比题解1要低(需要做更多次的选择)，但代价比题解1要低得多。综合起来，题解2总的工作量更少。

其实题解2的思路是与归并排序是完全相同的。你可以仔细对比一下。