• LeetCode HOT 100 —— 23.合并K个升序链表


    题目

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

    请你将所有链表合并到一个升序链表中,返回合并后的链表。
    在这里插入图片描述

    思路

    在做本题之前,先考虑一下,如何合并两个有序链表,见 21.合并两个有序链表

    最直接的思路就是,用一个变量ans,来维护合并后的链表,第i次循环将第i个链表和ans合并,答案存到ans中,从而实现合并k个链表的功能

    即相当于在 21.合并两个有序链表基础上加上一个for循环一次合并即可

    java代码如下:

    class Solution {
        public ListNode mergeKLists(ListNode[] list){
            ListNode ans = null;//初始化一个空节点,用来合并链表
            for(int i = 0; i < list.length; i++){
                ans = mergeTwoLists(ans,list[i]);
            }
            return ans;
        }
    
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(-1);//创建虚拟头结点
    
            ListNode prev = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    prev.next = l1;
                    l1 = l1.next;
                } else {
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
    
            // 合并后 l1 和 l2 最多只有一个还未被合并完,直接将链表末尾指向未合并完的链表即可
            prev.next = (l1 == null) ? l2 : l1;
    
            return dummy.next;//虚拟头结点的作用来了~
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    但是这种合并可以进行优化,主要有两种优化思路:

    思路一:分治合并

    • 将 k 个链表配对并将同一对中的链表合并;
    • 第一轮合并以后, k 个链表被合并成了 k / 2个链表,平均长度为 2n / k ,然后是 k / 4个链表, k / 8个链表等等;
    • 重复这一过程,直到得到了最终的有序链表。

    java代码如下:

    class Solution {
    	//合并k个链表
    	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 - l) / 2 ;//防止溢出
    		return mergeTwoLists(merge(lists, l , mid), merge(lists, mid + 1, r));//归并的核心
    	}
    	
    	//这一段仍然是合并两个链表的代码,没有任何变化
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(-1);//创建虚拟头结点
    
            ListNode prev = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    prev.next = l1;
                    l1 = l1.next;
                } else {
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
    
            // 合并后 l1 和 l2 最多只有一个还未被合并完,直接将链表末尾指向未合并完的链表即可
            prev.next = (l1 == null) ? l2 : l1;
    
            return dummy.next;//虚拟头结点的作用来了~
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    思路二:使用优先队列合并

    优先队列:在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。

    这里和前面的思路都不一样,用容量为K的优先队列(最小堆实现),把链表的头结点都放进去,然后出队当前优先队列中最小的,挂上链表,然后让出队的那个节点的下一个入队,再出队当前优先队列中最小的,直到优先队列为空。(这里优先队列的优先级就是用链表的节点值来表示的)

    java代码如下:

    class Solution {
    	public ListNode mergeKLists(ListNode[] lists){
    		
    		if(lists.length == 0){
    			return null;
    		}
    		
    		ListNode dummy = new ListNode(-1);//创建一个虚拟头结点,方便操作
    		ListNode cur = dummy;//声明当前节点指向虚拟头结点
    		PriorityQueue<ListNode> pq = new PriorityQueue<>((ListNode a, ListNode b) -> a.val - b.val);
    		
    		for(ListNode list : lists){
    			if(list == null){
    				continue;//如果为空则跳过
    			}
    			pq.add(list);//不为空则加入优先队列
    		}
    		
    		while(!pq.isEmpty()){
    			ListNode node = pq.poll();//出队列最小的节点
    			cur.next = node;//将该节点拼接到结果链表中
    			cur = cur.next;
    			if(node.next != null){//如果node下个节点不为空,则继续加入队列填补之前的空缺位置
    				pq.add(node.next);
    			}
    		}
    		return dummy.next;		
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
  • 相关阅读:
    头歌平台 第2关:整数四则运算表达式的输出格式控制
    【零基础学Java】第二十二篇 集合2(Set,Map,Collections工具类)
    ARM端部署PP-OCR_V3
    1526_AURIX TC275 BootROM下
    视频SDK,高效视频解决方案
    Zookeeper临时节点删除时机解析
    Android12之解封装NuMediaExtractor::setDataSource过程(四十七)
    B/S医院HIS绩效考核系统源码
    2-3.基金的估值,费用与会计
    Matlab如何提取论文插图中的渐变色?一招轻松搞定
  • 原文地址:https://blog.csdn.net/qq_39473176/article/details/128032881