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

https://oj.leetcode.com/problems/merge-k-sorted-lists/

思路1（naive）：1跟2合并，然后跟3合并，然后跟4合并，一直到k个合并完。

    复杂度：1,2合并访问2n个节点，12与3合并访问3n个节点，...，123~k-1与k合并访问kn个节点，总共遍历节点数目n(3+4+5+...+k)，O(nk^2)。

思路2：mergeSort的思想，K个链表先划分为合并两个k/2的链表，每个k/2的链表在划分为k/4的链表，一直到只剩一个或者两个链表。

    复杂度：T(k)=2T(k/2)+O(nk)，根据主定理（算法导论上有讲），复杂度为O(nklogk)。

思路3：维护一个大小为k的堆。每次取堆顶元素放到结果中，并把该元素的后继（如果有）放入堆中。

    复杂度：每个元素读取一次nk，堆操作logk，所以复杂度为O(nklogk)。

思路2代码：

public ListNode mergeKLists(ArrayList<ListNode> lists) {        if (lists == null)            return null;        return merge(lists, 0, lists.size() - 1);    }    private ListNode merge(ArrayList<ListNode> lists, int start, int end) {        if (start == end)            return lists.get(start);        int mid = (start + end) / 2;        ListNode one = merge(lists, start, mid);        ListNode two = merge(lists, mid + 1, end);        return mergeTwoLists(one, two);    }    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null)            return l2;        if (l2 == null)            return l1;        ListNode p1 = l1;        ListNode p2 = l2;        ListNode head = new ListNode(-1);        head.next = p1.val <= p2.val ? p1 : p2;        ListNode tail = head;        while (p1 != null && p2 != null) {            if (p1.val <= p2.val) {                tail.next = p1;                ListNode oldP1 = p1;                p1 = p1.next;                oldP1.next = null;                tail = oldP1;            } else {                tail.next = p2;                ListNode oldP2 = p2;                p2 = p2.next;                oldP2.next = null;                tail = oldP2;            }        }        if (p1 != null)            tail.next = p1;        if (p2 != null)            tail.next = p2;        return head.next;    }

思路3代码（加测试代码）：

import java.util.ArrayList;import java.util.Comparator;import java.util.PriorityQueue;import java.util.Random;public class Solution {    public ListNode mergeKLists(ArrayList<ListNode> lists) {        if (lists == null)            return null;        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(20, new Comparator<ListNode>() {            @Override            public int compare(ListNode o1, ListNode o2) {                return o1.val - o2.val;            }        });        ListNode head = new ListNode(-1);        ListNode cur = head;        for (int i = 0; i < lists.size(); i++) {            if (lists.get(i) != null)                pq.add(lists.get(i));        }        while (!pq.isEmpty()) {            ListNode out = pq.remove();            cur.next = out;            cur = cur.next;            if (out.next != null)                pq.add(out.next);        }        return head.next;    }    public static void main(String[] args) {        ArrayList<ListNode> lists = new ArrayList<ListNode>();        int k = 3;        for (int i = 0; i < k; i++) {            ListNode list = makeList(getRandomArray());            lists.add(list);            printList(list);        }        printList(new Solution().mergeKLists(lists));    }    private static int[] getRandomArray() {        Random rand = new Random();        int size = rand.nextInt(10);        int[] res = new int[size];        if (size == 0)            return res;        res[size - 1] = 100;        for (int i = size - 2; i >= 0; i--) {            res[i] = rand.nextInt(res[i + 1] + 1);        }        return res;    }    private static ListNode makeList(int[] a) {        ListNode head = new ListNode(-1);        ListNode p = head;        for (int i = 0; i < a.length; i++) {            p.next = new ListNode(a[i]);            p = p.next;        }        return head.next;    }    private static void printList(ListNode head) {        while (head != null) {            System.out.print(head.val);            if (head.next != null)                System.out.print("->");            head = head.next;        }        System.out.println();    }}class ListNode {    int val;    ListNode next;    ListNode(int x) {        val = x;        next = null;    }}

参考：

http://blog.csdn.net/linhuanmars/article/details/19899259

http://www.cnblogs.com/TenosDoIt/p/3673188.html