2.＜tag-链表和归并, 优先队列＞lt.21-合并两个有序链表 + lt.23-合并k个升序链表

lt.21-合并两个有序链表

[案例需求]

[思路分析]

结合归并排序中的sort方法, 即可写出这道简单题
两条链表list1, list2, 在两者均未遍历到null时, 相互比较, 符合要求的加入到新链表中.

[代码实现]

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        //合并两个有序链表
        /**
            剪枝:
                list1 == null && list2 == null return 任意
                list1 == null || list2 == null 分别返回
            比较大小
            list1.val < list2  list1加入新链表, list1的temp后移

            = 均加入, 均后移

            > list2 加入, 后移.        
         */

        if(list1 == null && list2 == null) return null;
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode temp1 = list1;
        ListNode temp2 = list2;
        ListNode dummyNode =  new ListNode(-1);
        ListNode temp = dummyNode;

        while(temp1 != null && temp2 != null){
            if(temp1.val <= temp2.val){
                 temp.next = temp1;
                temp1 = temp1.next;
                temp = temp.next;
            }else{
                temp.next = temp2;
                temp = temp.next;
                temp2 = temp2.next;
            }
        }

        if(temp1 != null)temp.next = temp1;
        if(temp2 != null)temp.next = temp2;

        return dummyNode.next;
    }
}

lt.23-合并k个升序链表[hard]

[案例需求]

[思路分析]

• 对于本题, 我们希望能够有一种数据结构, 把lists中的k条链表遍历后, 存入到其中, 在其中能够实现结点val之间的升序排列, 然后对这个数据结构遍历, 用next域把各个结点串起来即可, 想来想去, 最符合的就是优先队列(PriorityQueue)了, 它是一种基于堆(默认小顶堆)实现的数据结构.
• 使用优先队列的解法步骤如下:
  0. 定义优先队列, 根据我们的需要传入比较器参数, new一个comparator, 重写他的compare方法让他能够按照我们想要的方式进行排序
  1. 遍历lists, 把遍历到的每个节点添加到priorityQueue中.
  2. 上一步骤完成后, 遍历priorityQueue, 并用一个指向头结点dummyNode的指针p把他们串起来, 返回头结点即可.

[代码实现]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        //剪枝
        if(lists == null || lists.length == 0)return null;
        
        //新建一个优先队列, 对每一个list进行排序后加入到queue(优先队列后)
        //然后遍历这个queue, 把里面的每个节点按顺序连接起来
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
                @Override
                public int compare(ListNode node1, ListNode node2){
                    if(node1.val - node2.val > 0){
                         return 1;
                    }else if(node1.val - node2.val == 0){
                        return 0;
                    }else{
                        return -1;
                    }
                }
        });

        ListNode dummyNode = new ListNode(-1);
        ListNode temp = dummyNode;

        //存入lists 
        for(ListNode node : lists){
            if(node != null)queue.add(node);
        }

        //遍历queue, 连接节点
        while(queue.size() != 0){
            temp.next = queue.poll();
            temp = temp.next;
            if(temp.next != null) queue.add(temp.next); ///  ?????
        }

        return dummyNode.next;
    }
}

[思路分析二, 分治法]

待补充