Java实现 亚博体育LeetCode 23 合并K个排序链表

合并K个排序链表

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
Java实现 亚博体育LeetCode 23 合并K个排序链表

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

PS:直接用PriorityQueue自动排序,改写一下compare方法。

/**

  • Definition for singly-linked list.
  • public class ListNode {
  • int val;
  • ListNode next;
  • ListNode(int x) { val = x; }
  • }
    */
    class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

    if (lists.length == 0) {
        return null;
    }
    
    ListNode dummyHead = new ListNode(0);
    ListNode curr = dummyHead;
    PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    });
    
    for (ListNode list : lists) {
        if (list == null) {
            continue;
        }
        pq.add(list);
    }
    
    while (!pq.isEmpty()) {
        ListNode nextNode = pq.poll();
        curr.next = nextNode;
        curr = curr.next;
        if (nextNode.next != null) {
            pq.add(nextNode.next);
        }
    }
    return dummyHead.next;

    }
    }

PS:分治

/**

  • Definition for singly-linked list.
  • public class ListNode {
  • int val;
  • ListNode next;
  • ListNode(int x) { val = x; }
  • }
    */
    class Solution {
    public ListNode mergeKLists(ListNode[] lists){
    if(lists.length == 0)
    return null;
    if(lists.length == 1)
    return lists[0];
    if(lists.length == 2){
    return mergeTwoLists(lists[0],lists[1]);
    }

    int mid = lists.length/2;
    ListNode[] l1 = new ListNode[mid];
    for(int i = 0; i < mid; i++){
        l1[i] = lists[i];
    }
    
    ListNode[] l2 = new ListNode[lists.length-mid];
    for(int i = mid,j=0; i < lists.length; i++,j++){
        l2[j] = lists[i];
    }
    
    return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    ListNode head = null;
    if (l1.val <= l2.val){
        head = l1;
        head.next = mergeTwoLists(l1.next, l2);
    } else {
        head = l2;
        head.next = mergeTwoLists(l1, l2.next);
    }
    return head;

    }
    }
    4

相关推荐