LeetCode 23. 合并K个升序链表

红太狼 2022-10-28 10:06 182阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[官方题解][Link 1]

解法一：优先队列（无空间优化）
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            ListNode head = new ListNode(0);
            ListNode point = head;
            PriorityQueue<ListNode> q = new PriorityQueue<ListNode>((ListNode a, ListNode b)->{
        return a.val - b.val;});
            for(ListNode l : lists){
        
                if(l != null)
                    q.add(l);
            }
            while(!q.isEmpty()){
        
                ListNode tmp = q.poll();
                point.next = new ListNode(tmp.val);
                point = point.next;
                tmp = tmp.next;
                if(tmp != null)
                    q.add(tmp);
            }
            return head.next;
        }
    }

//解法二：按顺序合两两合并两个链表
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            ListNode ans = null;
            for(ListNode l : lists)
                ans = mergeTwoLists(ans, l);
            return ans;
        }
         public ListNode mergeTwoLists(ListNode a, ListNode b){
        
             if(a == null || b == null){
        
                 return a != null ? a : b;
             }
             ListNode head = new ListNode(0);
             ListNode tail = head, aPtr = a, bPtr = b;
             while(aPtr != null && bPtr != null){
        
                 if(aPtr.val < bPtr.val){
        
                     tail.next = aPtr;
                     aPtr = aPtr.next;
                 }else{
        
                     tail.next = bPtr;
                     bPtr = bPtr.next;
                 }
                 tail = tail.next;
             }
             if(aPtr != null)
                tail.next = aPtr;
            else
                tail.next = bPtr;
            return head.next;
         }
    }

//解法三：分治最快
    class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            return merge(lists, 0, lists.length - 1);
        }
    
        public ListNode merge(ListNode[] lists, int l, int r) {
        
            if (l == r) {
        
                return lists[l];
            }
            if (l > r) {
        
                return null;
            }
            int mid = (l + r) >> 1;
            return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
        }
    
        public ListNode mergeTwoLists(ListNode a, ListNode b) {
        
            if (a == null || b == null) {
        
                return a != null ? a : b;
            }
            ListNode head = new ListNode(0);
            ListNode tail = head, aPtr = a, bPtr = b;
            while (aPtr != null && bPtr != null) {
        
                if (aPtr.val < bPtr.val) {
        
                    tail.next = aPtr;
                    aPtr = aPtr.next;
                } else {
        
                    tail.next = bPtr;
                    bPtr = bPtr.next;
                }
                tail = tail.next;
            }
            tail.next = (aPtr != null ? aPtr : bPtr);
            return head.next;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/9e056e78d15047199f7058bdc61d8881.png
[Link 1]: https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/