题目

现有多个有序链表， 需要合并成一个有序链表
例如

1->2->3->4
1->3->4->5
3->6->7->8

合并后为：

1->2->3->3->3->4->4->5->6->7->8

import java.util.Comparator;
import java.util.PriorityQueue;

public class SortedLinkListMerge {
    public static void main(String[] args) {
        ListNode[] lists = buildListNodeArray();
        ListNode s = mergeKLists(lists);
        while (true) {
            if(s.next == null) {
                System.out.println(s.val);
                break;
            }else {
                System.out.print(s.val + "->");
                s = s.next;
            }
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        //用heap(堆)这种数据结构，也就是 java 里面的 PriorityQueue
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode a, ListNode b) {
                return a.val-b.val;
            }
        });
        ListNode ret = null, cur = null;
        //首先先将每个列表的第一个节点加到堆中
        for(ListNode node: lists) {
            if(null != node) {
                pq.add(node);
            }
        }
        while(!pq.isEmpty()) {
            //从堆中取出一个节点（肯定是最小的节点）
            ListNode node = pq.poll();
            if(null == ret) {
                //ret：为最后返回列表的头节点
                //cur：为当前处理节点
                ret = cur = node;
            }
            else {
                cur = cur.next = node;
            }
            if(null != node.next) {
                pq.add(node.next);
            }
            if(pq.size() ==1) {
                //如果最后堆只剩一个元素时，说明只剩下一个列表没有遍历完成，
                //则将剩余的支架加到列表尾就可以了。
                cur.next = pq.poll();
                break;
            }
        }
        return ret;
    }

    private static ListNode[] buildListNodeArray() {
        ListNode list1 = buildListNode(new int[]{1,2,3,4});
        ListNode list2 = buildListNode(new int[]{1,3,4,5});
        ListNode list3 =buildListNode(new int[]{3,6,7,8});
        return new ListNode[]{list1, list2, list3};
    }

    private static ListNode buildListNode(int[] ints) {
        ListNode header = new ListNode(ints[0]);
        if(ints.length >1) {
            ListNode pre = header;
            for (int i = 1; i < ints.length; i++) {
                ListNode node = new ListNode(ints[i]);
                pre.next = node;
                pre = node;
            }
        }
        return header;
    }

    static class ListNode{
        ListNode next;
        int val;

        public ListNode(int val) {
            this.val = val;
        }
    }
}