leetcode23合并k个升序链表

原题链接:
https://leetcode.cn/problems/merge-k-sorted-lists/

解法1: 堆

/**
 * 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 mergeKLists(ListNode[] lists) {
        // 最小堆 根据当前节点进行排序
        PriorityQueue<ListNode>heap = new PriorityQueue<>((o1,o2) ->{
            return o1.val - o2.val;
        });

        for(var node : lists){
            if(node != null){
                heap.offer(node);
            }   
        }

        ListNode dummy = new ListNode(0);

        ListNode cur = dummy;

        while (!heap.isEmpty()){
            var node = heap.poll();
            cur.next = node;
            cur = cur.next;
            if(node.next != null){
                heap.offer(cur.next);
            }
        }

        return dummy.next;

    }
}

解法2: 分治

class Solution {
    /*
    *  分治
    *  将要排序的链表不断二分 将左右两边都排序完之后再进行拼接
    * */
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeKLists(lists,0, lists.length);
    }

    // 合并 list[i] 到 list[j - 1] 的链表
    private ListNode mergeKLists(ListNode[] lists, int i, int j) {
        // 计算链表的长度
        int m = j - i;

        // m = 0 为空直接返回
        if(m == 0){
            return null;
        }

        // 只有一条链表直接返回无需排序
        // 因为是到 j - 1 左闭右开 区间 return i
        if(m == 1){
            return  lists[i];
        }

        // 划分
        var left = mergeKLists(lists,i, i + m / 2);
        var right = mergeKLists(lists,i + m / 2 , j);

        // 合并两条有序链表
        return mergeTwoLists(left,right);

    }


    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(list1 != null && list2!=null){
            if(list1.val < list2.val){
                cur.next = new ListNode(list1.val);
                list1 = list1.next;
            }else{
                cur.next = new ListNode(list2.val);
                list2 = list2.next;
            }

            cur = cur.next;
        }
        
        cur.next = list1 != null ? list1 : list2;
        
        return dummy.next;
    }
}