题目

代码分析

method1:使用优先级队列，堆的方式来控制三个链表的头
method2:归并排序的应用

代码展示

方法1 优先级队列

public static ListNode mergeKLists(ArrayList<ListNode> lists) {
        //小顶
        PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.value-o2.value;
            }
        });

        for(ListNode e:lists)
        {
            pq.add(e);
        }
        ListNode res=new ListNode(0);
        ListNode cur=res;
        while(!pq.isEmpty())
        {
            ListNode temp=pq.poll();
            cur.next=temp;
            cur=cur.next;
            if(temp.next!=null)
            {
                pq.add(temp.next);
            }
        }
        return res.next;
    }

方法2 归并排序的应用

   public ListNode mergeKLists(ArrayList<ListNode> lists)
    {
         if(lists==null||lists.size()==0){
           return null;
         }
        //init
        ListNode[] listArr=new ListNode[lists.size()];
        for(int i=0;i<listArr.length;i++)
        {
            listArr[i]=lists.get(i);
        }

        return mergeKLists(listArr,0,listArr.length-1);
    }

    public static ListNode mergeKLists(ListNode[] listArr,int left,int right)
    {
        if(left==right) return listArr[left];
        int mid=(left+right)/2;
        ListNode cur1=mergeKLists(listArr,left,mid);
        ListNode cur2=mergeKLists(listArr,mid+1,right);
        return mergeTwoLists(cur1,cur2);
    }   

    public static ListNode mergeTwoLists(ListNode head1,ListNode head2)
    {
        if(head1==null) return head2;
        if(head2==null) return head1;

        if(head1.val<head2.val)
        {
           head1.next=mergeTwoLists(head1.next,head2);
           return head1;
        }
        else
        {
            head2.next=mergeTwoLists(head1,head2.next);
            return head2;
        }
    }

完成情况

1次