LC023-合并K个升序链表

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      

利用堆做排序

需要一种辅助数据结构-​

​堆​

​，有了堆这个数据结构，难度等级是困难的题目，瞬间变成简单了。

只把k个链表的第一个节点放入到堆中

之后不断从堆中取出节点，如果这个节点还有下一个节点，

就将下个节点也放入堆中

public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        //创建一个最小的堆,并定义好内部排序
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return (o1.val - o2.val);
            }
        });

        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        //把每个链表的第一个节点放入到堆中
        for (int i = 0; i <lists.length ; i++) {
            ListNode head=lists[i];
            if (head!=null){
                queue.add(head);
            }
        }

        //  poll()把检索并删除此队列的头，如果此队列为空，则返回 null 。
        //之后不断从堆中取出节点，如果这个节点还有下一个节点，
        //就将下个节点也放入堆中
        while (queue.size()>0){
            ListNode node=queue.poll();
            cur.next=node;
            cur=cur.next;
            if (node.next!=null){
                queue.add(node.next);
            }
        }
        cur.next=null;
        return  dummy.next;



    }      

两两合并

public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode newList = lists[0];
        for (int i = 1; i < lists.length; i++) {
            newList = merge(newList, lists[i]);
        }
        return newList;
    }

//两两合并的代码，直接把下面这段代码拿来用即可
    public ListNode merge(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return (a == null) ? b : a;
        }
        if (a.val <= b.val) {
            a.next = merge(a.next, b);
            return a;
        } else {
            b.next = merge(a, b.next);
            return b;
        }
    }
}      

分治

分治就是不断缩小其规模，再不断合并扩大的过程

• 分治就是不断缩小其规模,在不断扩大的过程
• 一开始的数组的规模是6,我们找到中间点,将一分为二,然后再分,直到不能在分(规模为一),便返回
• 之后合并,合并接用合并两个排序链表的代码
• 当两个规模最小的链表合并完后,其规模就变大,
• 然后不断重复这个合并过程,直到最终得到一个有序的链表

package com.nie.LEE;

public class LEE023L {
    /*
    分治就是不断缩小其规模,在不断扩大的过程
    一开始的数组的规模是6,我们找到中间点,将一分为二,然后再分,直到不能在分(规模为一),
    便返回
    之后合并,合并接用合并两个排序链表的代码
    当两个规模最小的链表合并完后,其规模就变大,
    然后不断重复这个合并过程,直到最终得到一个有序的链表
      */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return  helper(lists,0,lists.length-1);
    }
    //通过mid将数组一分为二，并不断缩小规模，当规模为1时返回并开始合并
    //通过合并两个链表，不断增大其规模，整体看就是不断缩小-最后不断扩大的过程
    private ListNode helper(ListNode[] lists, int begin, int end) {
        if (begin==end){
            return  lists[begin];
        }
        int mid=begin+(end-begin)/2;
        ListNode left=helper(lists,begin,mid);
        ListNode right=helper(lists,mid+1,end);
        return  merge(left,right);
    }

合并两个有序链表
    public ListNode merge(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return (a == null) ? b : a;
        }
        if (a.val <= b.val) {
            a.next = merge(a.next, b);
            return a;
        } else {
            b.next = merge(a, b.next);
            return b;
        }
    }


    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;
        }
    }
}