23. 合并 K 个升序链表

￡神魔★判官ぃ 2024-02-24 01:53 58阅读 0赞

#### 文章目录 ####

*   *  1. 题目描述
     *  2. 涉及相关知识点
     *  3. 个人题解
     *  4. 优秀题解总结分析
     *  5. 知识点总结

### 1. 题目描述 ###

![在这里插入图片描述][d9bd37ff4d8b47c8ac4ee63357636854.png]

### 2. 涉及相关知识点 ###

*  链表
 *  归并排序
 *  分治算法

### 3. 个人题解 ###

> 我的思路很简单也很暴力，就是一次遍历lists数组，然后取出第一个不为空的listnode作为结果存放的地方，然后merge函数就是实现归并排序的。时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( 1 ) O(1) O(1)。

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            //lists为空直接输出空即可
            if(lists.length==0){
        
                return null;
            }
            //用来临时存放结果
            ListNode temp=lists[0];
            int tempnum=-1;
            for(int i=0;i<lists.length;i++){
        
               if(lists[i]!=null){
        
                   tempnum=i;
                   break;
               }
            } 
            //表示数组中所有链表都为空
            if(tempnum==-1){
        
                return null;
            }
            for(int i=tempnum+1;i<lists.length;i++){
        
                temp=merge(lists[tempnum],lists[i]);
                lists[tempnum]=temp;
            }     
            return lists[tempnum];    
        }
        //使用归并排序合并串
        public ListNode merge(ListNode l1,ListNode l2){
        
            ListNode midtemp;
            if(l2==null){
        
                return l1;
            }else{
        
                ListNode subtemp;
                if(l1.val > l2.val){
        
                    midtemp=l2;
                    subtemp=midtemp;
                    l2=l2.next;
                }else{
        
                    midtemp=l1;
                    subtemp=midtemp;
                    l1=l1.next;
                }
                while(l1!=null || l2!=null ){
        
                    if(l1==null){
        
                        subtemp.next=l2;
                        break;
                    }else if(l2==null){
        
                        subtemp.next=l1;
                        break;
                    }
                    if(l1.val >= l2.val){
        
                         subtemp.next=l2;
                         subtemp=subtemp.next;
                         l2=l2.next;
                    }else{
        
                         subtemp.next=l1;
                         subtemp=subtemp.next;
                         l1=l1.next;
                    }
                }
            }
            return midtemp;
        }
    }

### 4. 优秀题解总结分析 ###

*  方法一：分治合并

> 思路就是使用分治算法的思想，每一次合并两个链表，通过多次递归最后合并出我们的最终的结果

![在这里插入图片描述][4a254932bfac4e9ea5989d28359548fa.png]

> 下面对题解代码进行逐句分析

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
        //merge就是我们实际用来归并链表的函数，初始归并的范围为0～lists.length - 1（也就是lists数组中第一个元素和最后一个元素）
            return merge(lists, 0, lists.length - 1);
        }
        //merge函数就是我们实际用来归并链表的函数
        public ListNode merge(ListNode[] lists, int l, int r) {
        
            //l==r表示，当前只有一个元素来（即范围的开始l=范围的结束r）
            if (l == r) {
        
                //此时我们就得到了我们的归并结果
                return lists[l];
            }
            //特殊情况排除在外
            if (l > r) {
        
                return null;
            }
            //左移乘2右移除2，得到l～r范围内的中间元素所在的位置
            int mid = (l + r) >> 1;
            //一中间元素为分割点，然后递归调用merge函数
            return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
        }
        //这里就开始真正的归并排序了
        public ListNode mergeTwoLists(ListNode a, ListNode b) {
        
            //注意题目条件，lists汇总元素是允许为空的
            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;
        }
    }

![在这里插入图片描述][30720f0143e3433fadf723cdd0004918.png]

> 上面代码的核心就是一个分治算法，和归并排序

*  方法二：使用优先队列合并

这个方法和前两种方法的思路有所不同，我们需要维护当前每个链表没有被合并的元素的最前面一个，kk个链表就最多有 k个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。

class Solution {
        
        //Status这个类实现了比较器接口Comparable，然后在类中实现compareTo方法
        class Status implements Comparable<Status> {
        
            int val;
            ListNode ptr;
    
            Status(int val, ListNode ptr) {
        
                this.val = val;
                this.ptr = ptr;
            }
    
            public int compareTo(Status status2) {
        
                return this.val - status2.val;
            }
        }
        //定义一个优先队列
        PriorityQueue<Status> queue = new PriorityQueue<Status>();
        //下面的代码就是最晦涩难懂的地方了
        public ListNode mergeKLists(ListNode[] lists) {
        
            //遍历lists数组
            for (ListNode node: lists) {
        
                //将不为空的链表放到优先队列中，并将每个链表的定义转换为Status类
                if (node != null) {
        
                    queue.offer(new Status(node.val, node));
                }
            }
            //head，tail是用来定义最终的结果链表的，head执行链表头部，tail指向链表尾部
            ListNode head = new ListNode(0);
            ListNode tail = head;
            while (!queue.isEmpty()) {
        
                Status f = queue.poll();
                tail.next = f.ptr;
                tail = tail.next;
                if (f.ptr.next != null) {
        
                    queue.offer(new Status(f.ptr.next.val, f.ptr.next));
                }
            }
            return head.next;
        }
    }

> 其实上面的解法就是利用了优先队列的特性，使用节点的val为优先级的判定条件，val越小优先级就越大，然后每次弹出优先级最高的元素加入结果链表，最后就可以实现从小到大排序

![在这里插入图片描述][70dd14ad14514e0a864392fcf2229694.png]

### 5. 知识点总结 ###

*  java比较器的实现

**实现Comparator接口**  
上面代码就是采用这种方法实现的

import java.util.Comparator;
    
    public class MyComparator implements Comparator<Integer> {
        
        @Override
        public int compare(Integer o1, Integer o2) {
        
            // 按照降序排列
            return o2.compareTo(o1);
        }
    }

**使用Lambda表达式**  
如果你只需要在一个特定的地方定义一个比较器，你可以使用匿名内部类或Lambda表达式来实现它，而无需创建一个独立的类。这种方法通常用于一次性或临时的比较器。

import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class ComparatorExample {
        
        public static void main(String[] args) {
        
            PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
        
                @Override
                public int compare(Integer o1, Integer o2) {
        
                    // 按照降序排列
                    return o2.compareTo(o1);
                }
            });
    
            pq.offer(5);
            pq.offer(2);
            pq.offer(8);
            pq.offer(1);
        }
    }

*  java优先队列

**定义**

Java中的PriorityQueue是一种优先队列数据结构，它基于堆（Heap）实现，用于存储和管理具有优先级的元素集合。优先队列允许你插入元素，并在任何时候取出具有最高（或最低）优先级的元素。如果元素实现了Comparable接口，那么它们的优先级就由compareTo()方法来确定。PriorityQueue会根据这个方法的返回值来排序元素，使得根节点具有最小（或最大，根据你的比较器定义）值。例如，对于整数元素的PriorityQueue，默认情况下会按升序排列。（上面的代码就是实现了CompareTo函数，然后通过结点的val来判断元素的优先级）

**底层实现**  
PriorityQueue的底层实现是二叉堆（Binary Heap），通常是一个最小堆（Min Heap）。

**常用方法**

*  插入元素：通过offer()方法或add()方法将元素插入队列。
 *  获取并移除最高优先级的元素：使用poll()方法。
 *  获取但不移除最高优先级的元素：使用peek()方法。
 *  确定队列是否为空：使用isEmpty()方法。
 *  获取队列的大小：使用size()方法。

[d9bd37ff4d8b47c8ac4ee63357636854.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/075e7e434a29472da422fc9bbd4fddee.png
[4a254932bfac4e9ea5989d28359548fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/c2624ea4cba54057a5894abb160d165d.png
[30720f0143e3433fadf723cdd0004918.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/cf75865087a243df981acb2e7f4568cd.png
[70dd14ad14514e0a864392fcf2229694.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/1aecf85a7793422297c22c640293c707.png