【LeeCode23】Merge k Sorted Lists★★★

624 0 0

作者:追梦boy

1.题目描述：

2.解题思路：

　　题意：将K个已经排序的链表合并成一个排序的链表，分析并描述所用算法的复杂度。

　　方法一：基于“二分”思想的归并排序。本文用非递归和递归两种方法实现。

　　（1）非递归：归并排序”（Merging Sort）：将两个或两个以上的有序表组合成一个新的有序表，无论是顺序存储结构还是链式存储结构，对于任何两个长度分别为m和n的有序表，其组合都可在O(m+n)的时间复杂度量级上完成。对于K个有序表，假设共有N个元素，且这些有序表初始状态都不为空，每个有序表平均拥有N/K个元素。最常用的方法是采用“二分”的思想进行两两合并：第一轮循环，有序表lists[0]与lists[(K+1)/2]，lists[1]与lists[(K+1)/2+1]，lists[2]与lists[(K+1)/2+2]....，lists[K/2-1]与lists[K-1]。这样K个有序表就被组合成了K/2个有序表；第二轮循环后将减少为K/4个有序表；直到组合成一个具有N个元素的有序表。总的时间复杂度：O(NKlogK)。

　　（2）递归：思想和上面类似，用的是递归实现。

　　方法二：基于优先级队列的“堆排序”。

　　在Java中，堆是一种可以自我调整的二叉树，对于最小堆来说，对树执行删除和添加操作，可以让最小元素移动到根节点。在Java中，优先级队列（Priority Queue）便采用了“堆”这种数据结构，PriorityQueue是一个泛型类，它可以保存实现了Comparable接口的类对象，也可以保存在构造器中提供比较器的对象（优先级队列实现排序中也需要比较）。

基于优先级队列，我们可以将K个链表的头结点全部添加到队列，由于优先级队列采用了最小堆数据结构，堆顶为队列的最小元素，我们将其取出添加到结果链表中，取出元素对应的链表下移一个节点，并将这个节点添加到优先级队列中；然后我们继续取出堆顶元素，...，直到优先级队列为空，那么其中所有元素取尽，K个链表的元素已经全部排序到结果链表。

3.Java代码：

（1）归并排序：非递归

 1 //public class LeetCode23 为测试代码
 2 public class LeetCode23 {
 3     public static void main(String[] args) {
 4         ListNode[] lists=new  ListNode[3];
 5         ListNode a1=new ListNode(1);
 6         ListNode a2=new ListNode(4);
 7         ListNode a3=new ListNode(7);
 8         a1.next=a2;
 9         a2.next=a3;
10         System.out.println("链表a:"+a1.val+"->"+a2.val+"->"+a3.val);
11         ListNode b1=new ListNode(2);
12         ListNode b2=new ListNode(5);
13         ListNode b3=new ListNode(8);
14         b1.next=b2;
15         b2.next=b3;
16         System.out.println("链表b:"+b1.val+"->"+b2.val+"->"+b3.val);
17         ListNode c1=new ListNode(3);
18         ListNode c2=new ListNode(6);
19         ListNode c3=new ListNode(9);
20         c1.next=c2;
21         c2.next=c3;
22         System.out.println("链表c:"+c1.val+"->"+c2.val+"->"+c3.val);
23         lists[0]=a1;
24         lists[1]=b1;
25         lists[2]=c1;
26         ListNode result=new Solution().mergeKLists(lists);
27         if(result!=null){
28             System.out.print("结果链表:"+result.val);
29             ListNode resultNext=result.next;
30             while(resultNext!=null){
31                  System.out.print("->"+resultNext.val);
32                  resultNext=resultNext.next;
33              }
34         }
35        
36     }
37 }
38 
39 //class Solution为ac代码
40 class Solution {
41 public ListNode mergeKLists(ListNode[] lists) {
42     int len=lists.length;
43     if(lists==null||len==0) return null;    
44     while(len>1){
45         int mid=(len+1)/2;//len+1是为了在len为奇数时，mid恰好是正中间那一个
46         for(int i=0;i<len/2;i++){
47             lists[i]=merge2Lists(lists[i],lists[mid+i]);
48         }
49         len=mid;
50     }
51     return lists[0];
52     }
53 
54 private ListNode merge2Lists(ListNode l1, ListNode l2) {
55     if(l1==null) return l2;
56     if(l2==null) return l1;
57     if(l1.val<l2.val){
58         l1.next=merge2Lists(l1.next, l2);
59         return l1;
60     }
61     else{
62         l2.next=merge2Lists(l1, l2.next);
63         return l2;
64     }
65 }
66 }
67 class ListNode {
68     int val;
69     ListNode next;
70     ListNode(int x) { val = x; }
71     }

测试结果：

（2）归并排序：递归

 1 public class LeetCode23 {
 2     public static void main(String[] args) {
 3         ListNode[] lists=new  ListNode[3];
 4         ListNode a1=new ListNode(1);
 5         ListNode a2=new ListNode(4);
 6         ListNode a3=new ListNode(7);
 7         a1.next=a2;
 8         a2.next=a3;
 9         System.out.println("链表a:"+a1.val+"->"+a2.val+"->"+a3.val);
10         ListNode b1=new ListNode(2);
11         ListNode b2=new ListNode(5);
12         ListNode b3=new ListNode(8);
13         b1.next=b2;
14         b2.next=b3;
15         System.out.println("链表b:"+b1.val+"->"+b2.val+"->"+b3.val);
16         ListNode c1=new ListNode(3);
17         ListNode c2=new ListNode(6);
18         ListNode c3=new ListNode(9);
19         c1.next=c2;
20         c2.next=c3;
21         System.out.println("链表c:"+c1.val+"->"+c2.val+"->"+c3.val);
22         lists[0]=a1;
23         lists[1]=b1;
24         lists[2]=c1;
25         ListNode result=new Solution().mergeKLists(lists);
26         if(result!=null){
27             System.out.print("结果链表:"+result.val);
28             ListNode resultNext=result.next;
29             while(resultNext!=null){
30                  System.out.print("->"+resultNext.val);
31                  resultNext=resultNext.next;
32              }
33         }
34        
35     }
36 }
37 class Solution {
38 public ListNode mergeKLists(ListNode[] lists) {
39     int len=lists.length;
40     if(lists==null||len==0) return null;    
41     return partion(lists,0,len-1);
42     }
43 
44 private ListNode partion(ListNode[] lists, int start, int end) {
45     if(start==end) return lists[start];
46     if(start<end){
47         int mid=(start+end)/2;
48         ListNode left=partion(lists, start, mid);
49         ListNode right=partion(lists, mid+1, end);
50         return merge2Lists(left, right);
51     }else
52         return null;
53     
54 }
55 
56 private ListNode merge2Lists(ListNode l1, ListNode l2) {
57     if(l1==null) return l2;
58     if(l2==null) return l1;
59     if(l1.val<l2.val){
60         l1.next=merge2Lists(l1.next, l2);
61         return l1;
62     }
63     else{
64         l2.next=merge2Lists(l1, l2.next);
65         return l2;
66     }
67 }
68 }
69 class ListNode {
70     int val;
71     ListNode next;
72     ListNode(int x) { val = x; }
73     }

测试结果：

（3）堆排序

 1 import java.util.Comparator;
 2 import java.util.PriorityQueue;
 3 
 4 //public class LeetCode23 为测试代码
 5 public class LeetCode23{
 6     public static void main(String[] args) {
 7         ListNode[] lists=new  ListNode[3];
 8         ListNode a1=new ListNode(1);
 9         ListNode a2=new ListNode(4);
10         ListNode a3=new ListNode(7);
11         a1.next=a2;
12         a2.next=a3;
13         System.out.println("链表a:"+a1.val+"->"+a2.val+"->"+a3.val);
14         ListNode b1=new ListNode(2);
15         ListNode b2=new ListNode(5);
16         ListNode b3=new ListNode(8);
17         b1.next=b2;
18         b2.next=b3;
19         System.out.println("链表b:"+b1.val+"->"+b2.val+"->"+b3.val);
20         ListNode c1=new ListNode(3);
21         ListNode c2=new ListNode(6);
22         ListNode c3=new ListNode(9);
23         c1.next=c2;
24         c2.next=c3;
25         System.out.println("链表c:"+c1.val+"->"+c2.val+"->"+c3.val);
26         lists[0]=a1;
27         lists[1]=b1;
28         lists[2]=c1;
29         ListNode result=new Solution().mergeKLists(lists);
30         if(result!=null){
31             System.out.print("结果链表:"+result.val);
32             ListNode resultNext=result.next;
33             while(resultNext!=null){
34                  System.out.print("->"+resultNext.val);
35                  resultNext=resultNext.next;
36              }
37         }
38        
39     }
40 }
41 
42 //class Solution为ac代码
43 class Solution {
44 public ListNode mergeKLists(ListNode[] lists) {
45     if(lists==null||lists.length==0) return null;
46     if(lists.length==1) return lists[0];
47     PriorityQueue<ListNode> queue=new PriorityQueue<ListNode>(1, new Comparator<ListNode>() {
48         public int compare(ListNode l1,ListNode l2){
49             return l1.val-l2.val;
50         }
51     });
52     for(ListNode list:lists){
53         if(list!=null) 
54             queue.offer(list);
55     }
56     ListNode head=new ListNode(0);//建一个辅助结点作为最终所求链表的头节点
57     ListNode p=head;
58     while(!queue.isEmpty()){
59         ListNode node=queue.poll();
60         p.next=node;
61         p=p.next;
62         if(node.next!=null) queue.offer(node.next);
63     }
64     return head.next;
65     }
66 }
67 class ListNode {
68     int val;
69     ListNode next;
70     ListNode(int x) { val = x; }
71     }

测试结果：

内容来源于网络如有侵权请私信删除

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

【LeeCode23】Merge k Sorted Lists★★★