【题目】

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

合并几个有序链表为一个，分析算法复杂度。

【分治】

直观的想法是两两合并，有两种方法：1）list1和list2合并为newlist2，newlist2再和list3合并为newlist3，newlist3再和list4合并为newlist4……依次类推；2）list1和list2合并为list12，list3和list4合并为list34……然后list12再和list34合并……直到合并为一个list。

那么这两种方法有什么区别？

参考博客 http://www.cnblogs.com/TenosDoIt/p/3673188.html 得知，这两种方法时间复杂度并不一样，关键在于链表是有长度的。

方法1：1、2合并，遍历2n个节点；12结果和3合并，遍历3n个节点；123结果和4合并，遍历4n个节点；…… 123..k-1结果和k合并，遍历kn个节点；总共遍历的节点数目为n(2+3+…+k) = n*(k^2+k-2)/2, 因此时间复杂度是O(n*(k^2+k-2)/2) = O(nk^2)。

方法2：就是分治，算法复杂度为T(k) = 2T(k/2) + O(nk),很简单可以推导得到算法复杂度为O(nklogk)。

其实个人觉得，两种方法的区别就在于方法2每次合并的两个链表长度都比较接近，不管原始链表长度是否比较均等，最起码比方法1每次合并的两个链表长度之差小。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() < 1) return null;
        return mergeLists(lists, 0, lists.size() - 1);
    }
    
    
    public ListNode mergeLists(List<ListNode> lists, int from, int to) {
        if (from < to) {
            int mid = (from + to) / 2;
            return merge2Lists(mergeLists(lists, from, mid), mergeLists(lists, mid + 1, to));
        }
        return lists.get(from);
    }
    
    
    public ListNode merge2Lists(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        
        ListNode newHead = head1;
        ListNode node1 = head1, node2 = head2;
        if (head1.val > head2.val) {
            node1 = head2;
            node2 = head1;
            newHead = head2;
        }
        
        while (node1.next != null && node2 != null) {
            if (node2.val < node1.next.val) {
                ListNode tmp = node2.next;
                node2.next = node1.next;
                node1.next = node2;
                node1 = node1.next;
                node2 = tmp;
            } else {
                node1 = node1.next;
            }
        }
        
        if (node2 != null) {
            node1.next = node2;
        }
        
        return newHead;
    }
    
}

【优先队列】

维护一个优先级队列，把所有链表的头结点也就是最小的结点放入队列中，每次从队列中取出最小的元素，然后再把原链表中该元素后面的结点加入优先队列，直到队列为空。

把结点加入优先队列的时间复杂度为O(lgk)，总共kn个结点，所以总的时间复杂度为O(knlgk)，与分治一样。

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() < 1) return null;
        
        Comparator<ListNode> cmp =  new Comparator<ListNode>() { 
    	    public int compare(ListNode node1, ListNode node2) {
    	        return node1.val - node2.val;
    	    }
    	};
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), cmp);
        
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                queue.offer(lists.get(i));
            }
        }
        
        ListNode newHead = new ListNode(0);
        ListNode pre = newHead;
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            if (cur.next != null) {
                queue.offer(cur.next);
            }
            pre.next = cur;
            pre = pre.next;
        }
        
        return newHead.next;
    }
}

参考来源：http://blog.csdn.net/linhuanmars/article/details/19899259 

【LeetCode】Merge k Sorted Lists 解题报告