LeetCode : 23. Merge k Sorted Lists 合并K个有序链表

青旅半醒 2021-06-11 15:14 393阅读 0赞

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

Example:

Input:  
\[  
1->4->5,  
1->3->4,  
2->6  
\]  
Output: 1->1->2->3->4->4->5->6  
**代码：**  
归并算法的合并，但存在一个问题是我们需要比较K的数的大小，所以可以使用小顶堆进行排序。  
时间复杂度：O(Nlogk) 其中N是最终链表长度，k是链表数量

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> que = new PriorityQueue<>( (a,b)->a.val-b.val );
            for(int i =0; i<lists.length; i++){
                if(lists[i]!=null)
                    que.offer(lists[i]);
            }
            ListNode head = new ListNode(0);
            ListNode cur = head;
            while(!que.isEmpty()){
                ListNode tmp = que.poll();
                cur.next = tmp;
                cur = cur.next;
                if(tmp.next!=null)
                    que.offer(tmp.next);
            }
            if(head.next!=null)
                return head.next;
            else
                return null;
        }
    }

两两合并，分治策略。  
时间复杂度：  
K个链表分治次数logk；每个合并需要N。  
![在这里插入图片描述][20190418180046526.png]

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists==null || lists.length==0) return null;
            int num = lists.length;
            if(num==1) return lists[0];
            
            int left = 0, right = num-1;
            while(left<right){
                while(left<right){
                    lists[left] = merge(lists[left], lists[right]);
                    left++;
                    right--;
                }
                left = 0;
            }
            return lists[0];
        }
        
        public ListNode merge(ListNode a, ListNode b){
            ListNode out = new ListNode(0);
            ListNode head = out;
            while(a!=null && b!=null){
                if(a.val<=b.val){
                    out.next = a;
                    a = a.next;
                }else{
                    out.next = b;
                    b = b.next;
                }
                out = out.next;
            }
            while(a!=null){
                out.next = a;
                a = a.next;
                out = out.next;
            }
            while(b!=null){
                out.next = b;
                b = b.next;
                out = out.next;
            }
            return head.next;
        }
    }

[20190418180046526.png]: /images/20210520/38de48a8a1f440c79859146e8115ff29.png