首页 > 代码库 > 23. Merge k Sorted Lists

23. Merge k Sorted Lists

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

本题目我第一个想到了用小顶堆来做,不是很难,直接上代码:

<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>

/**

 * 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==null||lists.length==0) return null;

        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){

            public int compare(ListNode a,ListNode b){

                return a.val-b.val;

            }

        });

        for(ListNode l:lists){

            if(l!=null) q.offer(l);

        }

        ListNode node = new ListNode(0);

        ListNode dummy = node;

        while(!q.isEmpty()){

            ListNode next = q.poll();

            node.next = next;

            node = node.next;

            next = next.next;

            if(next!=null) q.offer(next);

        }

        return dummy.next;

    }

}

后来看了标签,发现还可以用分治的方法来做(也就是递归),代码如下:

<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>

/**

 * 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];

        if(lists.length==2) return mergeTwoLists(lists[0],lists[1]);

        return mergeTwoLists(mergeKLists(Arrays.copyOfRange(lists,0,lists.length/2)),mergeKLists(Arrays.copyOfRange(lists,lists.length/2,lists.length)));

    }

    public ListNode mergeTwoLists(ListNode l1,ListNode l2){

        ListNode node = new ListNode(0);

        ListNode dummy =node;

        while(l1!=null&&l2!=null){

            if(l1.val<l2.val){

                ListNode next = l1;

                node.next = next;

                node = node.next;

                l1 = l1.next;

            }else{

                ListNode next = l2;

                node.next = next;

                node = node.next;

                l2 = l2.next;

            }

        }

        if(l1!=null){

            node.next = l1;

        }

        if(l2!=null){

            node.next = l2;

        }

        return dummy.next;

    }

}

23. Merge k Sorted Lists