LCR 078. 合并 K 个升序链表

https://leetcode.cn/problems/vvXgSW/description/https://leetcode.cn/problems/vvXgSW/description/

解题思路

方法一：

每个链表维护一个索引，每次找到值最小的节点，索引加一。可以采用优先队列实现。

/**
 * 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> pq = new PriorityQueue<>((a,b)->a.val-b.val);//最小堆
        ListNode head=new ListNode();
        ListNode now=head;
        for(ListNode node:lists){
            if(node!=null){
                pq.offer(node);
            }
        }
        while(!pq.isEmpty()){
            ListNode top =pq.poll();//取出最小值
            now.next=top;
            now=top;
            top=top.next;
            if(top!=null){
                pq.offer(top);//加入下一个
            }
        }
        return head.next;
    }
}

方法二：

归并排序，先将链表数组二分，直到只有一个，后序两两合并。

/**
 * 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 {
    ListNode merge(ListNode[] lists,int l,int r){
    if(l==r){
        return lists[l];
    }
    int mid=(l+r)/2;
    ListNode left=merge(lists,l,mid);
    ListNode right=merge(lists,mid+1,r);
    ListNode head=new ListNode(),now=head;
    while(left!=null||right!=null){        //后序合并
        if(left==null||(right!=null&&left.val>right.val)){
            now.next=right;
            now=right;
            right=right.next;
        }
        else{
            now.next=left;
            now=left;
            left=left.next;
        }
    }
    return head.next;
}
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0){
            return null;
        }
        return merge(lists,0,lists.length-1);
    }
}