【腾讯精选练习 50 题】20—合并K个升序链表【困难】

ゝ一纸荒年。 2023-01-17 13:57 159阅读 0赞

### 文章目录 ###

*   *  题目链接
     *  题目简介
     *  题目解析
     *  题目代码

## 题目链接 ##

[23. 合并K个升序链表][23. _K]

## 题目简介 ##

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：
    
    输入：lists = [[1,4,5],[1,3,4],[2,6]]
    输出：[1,1,2,3,4,4,5,6]
    解释：链表数组如下：
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    将它们合并到一个有序链表中得到。
    1->1->2->3->4->4->5->6

## 题目解析 ##

*  题目有两种实现方法：最小堆和归并思想
 *  最小堆：
    
     *  利用 `Queue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);` 生成一个最小堆
     *  将我们 `lists` 遍历一遍，放入我们的最小堆中
     *  利用 `minListNode = queue.poll()`取出最小的，判断其 `next` 是否为空，从而判断是否添加至 ·queue·
     *  最后返回 `newListNode` 即可
 *  归并：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]
 *  首先，我们必须要会两个有序链表的合并，详情请见：[【 腾讯精选练习 50 题】12—合并两个有序链表【简单】][_ 50 _12]
 *  和归并排序差不多，两两归并，最后返回即可

## 题目代码 ##

*  最小堆

public ListNode mergeKLists(ListNode[] lists) {
        
            // 最小堆的做法
            Queue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
            for(ListNode listNode : lists){
        
                if(listNode != null){
        
                    queue.offer(listNode);
                }
            }
            ListNode newNode = new ListNode(0);
            ListNode p1 = newNode;
            while (!queue.isEmpty()){
        
                ListNode minListNode = queue.poll();
                p1.next = minListNode;
                p1 = p1.next;
                if(minListNode.next != null){
        
                    queue.offer(minListNode.next);
                }
            }
            return newNode;
        }

*  归并

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            // 类似归并排序
            // 先对于 1 2 、3 4 、5 6
            return merge(lists, 0, lists.length - 1);
        }
    
        public ListNode merge(ListNode[] lists, int left, int right){
        
            if(left == right){
        
                return lists[left];
            }
            if(left > right){
        
                return null;
            }
    
            int mid = (right - left) / 2 + left;
            // 获取左边归并的链表
            // 获取右边归并的链表
            ListNode node1 = merge(lists, left, mid);
            ListNode node2 = merge(lists, mid + 1, right);
            // 最后统一进行归并
            return mergeTwoListNode(node1, node2);
        }
    	// 两个有序链表的归并
        public ListNode mergeTwoListNode(ListNode node1, ListNode node2){
        
            if(node1 == null){
        
                return node2;
            }
            if(node2 == null){
        
                return node1;
            }
            ListNode newNode = new ListNode(0);
            ListNode p1 = newNode;
            while(node1 != null && node2 != null){
        
                if(node1.val <= node2.val){
        
                    newNode.next = node1;
                    node1 = node1.next;
                    newNode = newNode.next;
                }else{
        
                    newNode.next = node2;
                    node2 = node2.next;
                    newNode = newNode.next;
                }
            }
    
            while(node1 != null){
        
                newNode.next = node1;
                node1 = node1.next;
                newNode = newNode.next;
            }
    
            while(node2 != null){
        
                newNode.next = node2;
                node2 = node2.next;
                newNode = newNode.next;
            }
    
            return p1.next;
        }
    }

[23. _K]: https://leetcode-cn.com/problems/merge-k-sorted-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221021/e6d8e09976224aa89be44a87e898d1e2.png
[_ 50 _12]: https://blog.csdn.net/qq_40915439/article/details/115405586?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161970324516780265427341%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=161970324516780265427341&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v2~rank_v29-6-115405586.nonecase&utm_term=%E6%9C%89%E5%BA%8F