Question:

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

 

Analysis:

合并k个排好序的链表，返回最终一个总的排序列表。分析并描述他的复杂度。limited

思路一：我的思路是，设置一个头结点，然后申请一个数组，记录该位置的这组链表是否全部放入新的链表中。不再使用额外的空间，直接用原来的节点。测试了所有情况，都通过了，不过好可惜，time limit exceeded..可能因为我的方法，遍历n次，每次从里面选出最小的一个，所以导致时间复杂度为O(n2).

代码:

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    private ListNode tail;            public ListNode mergeKLists(ListNode[] lists) {        if(lists.length == 0)            return null;        if(lists.length == 1)            return lists[0];                int l = 0;        for(int i=0; i

思路二：使用归并排序（Merge Sort）算法。是一个比较经典的O(nlogn)的排序算法。思路是先分成两个子任务，然后递归求子任务，最后回溯回来。这个题目也是这样，先把k个list分成两半，然后继续划分，知道剩下两个list就合并起来，合并时会用到Merge Two Sorted Lists这道题.

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {        //用归并排序的方法    public ListNode mergeKLists(ListNode[] lists) {        if(lists.length == 0)            return null;        if(lists.length == 1)            return lists[0];                int l = 0;        for(int i=0; i

总结：遇到这种把n个排好序的东西混合成一个时，要立马想到归并排序。递归+回溯的方法！！