合并 k 个排序链表

傷城~ 2022-04-22 11:46 164阅读 0赞

合并 *k *个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

**示例:**

输入:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    输出: 1->1->2->3->4->4->5->6

思路：就是合并排序，把每个链表看成数组的一个数，再两两比较，排序，最后返回排序合并的结果。

代码：

package arithmetic.test11_14;
    
    import java.util.Arrays;
    
    class ListNode{
    	int val;
    	ListNode next;
    	
    	public ListNode(int val) {
    		this.val=val;
    	}
    }
    
    public class MergeList {
    	
    	private static ListNode first=null;
    	private static ListNode second=null;
    	private static ListNode three=null;
    	
    	/**
    	 * 链表插入数据
    	 * @param val
    	 */
    	 public void addNode(int val){
    	        ListNode newNode=new ListNode(val);
    	        if(first==null){
    	        	first=newNode;
    	            return;
    	        }
    	        ListNode tmp=first;
    	        while(tmp.next!=null){
    	            tmp=tmp.next;
    	        }
    	        //add Node to end
    	        tmp.next=newNode;
    	    }
    	 
    	 public void addNode2(int val){
    	        ListNode newNode=new ListNode(val);
    	        if(second==null){
    	        	second=newNode;
    	            return;
    	        }
    	        ListNode tmp=second;
    	        while(tmp.next!=null){
    	            tmp=tmp.next;
    	        }
    	        //add Node to end
    	        tmp.next=newNode;
    	    }
    	 
    	 public void addNode3(int val){
    	        ListNode newNode=new ListNode(val);
    	        if(three==null){
    	        	three=newNode;
    	            return;
    	        }
    	        ListNode tmp=three;
    	        while(tmp.next!=null){
    	            tmp=tmp.next;
    	        }
    	        //add Node to end
    	        tmp.next=newNode;
    	    }
    	
    	 /**
    	  * 输出整个链表
    	  * @param head
    	  * @param indexName
    	  */
    	public void printNode(ListNode head,String indexName){
    		System.out.println(indexName);
    		while(head!=null){
    			System.out.print(head.val+" ");
    			head=head.next;
    		}
    		System.out.println();
    	}
    	
    	public static void main(String[] args) {
    		MergeList ml=new MergeList();
    		ListNode[] lists=new ListNode[3];
    		for(int i=1;i<4;i++){
    			ml.addNode(i);
    		}
    		for(int i=2;i<5;i++){
    			ml.addNode2(i);
    		}
    		for(int i=3;i<6;i++){
    			ml.addNode3(i);
    		}
    		ml.printNode(first,"first链表");
    		ml.printNode(second,"second链表");
    		ml.printNode(three,"three链表");
    		
    		lists[0]=first;
    		lists[1]=second;
    		lists[2]=three;
    		ListNode mergeNode=ml.mergeKLists(lists);
    		ml.printNode(mergeNode,"merge链表");
    	}
    	
    	/**
    	 * 合并链表
    	 * @param lists
    	 * @return
    	 */
    	public ListNode mergeKLists(ListNode[] lists) {
            return partition(lists, 0, lists.length - 1);
        }
    	
    	/**
    	 * 分治思想。两两比较排序再合并
    	 * @param lists
    	 * @param start
    	 * @param end
    	 * @return
    	 */
        public ListNode partition(ListNode[] lists, int start, int end) {
            if (start == end) {
                return lists[start];
            }
    
            if (start < end) {
                int mid = (start + end) / 2;
                ListNode l1 = partition(lists, start, mid);
                ListNode l2 = partition(lists, mid + 1, end);
                return mergeTwoLists(l1, l2);
            }
    
            return null;
        }
        
        /**
         * 两个链表进行比较合并
         * @param l1
         * @param l2
         * @return
         */
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l2 == null) return l1;
            if (l1 == null) return l2;
    
            if (l1.val < l2.val) {
                ListNode tmp = l1;
                tmp.next = mergeTwoLists(l1.next, l2);
                return tmp;
            } else {
                ListNode tmp = l2;
                tmp.next = mergeTwoLists(l1, l2.next);
                return tmp;
            }
        }
    
    }

效果：

first链表  
1 2 3   
second链表  
2 3 4   
three链表  
3 4 5   
merge链表  
1 2 2 3 3 3 4 4 5

###  我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。 ###