LeetCode 23. Merge k Sorted Lists-蒲公英云

LeetCode 23. Merge k Sorted Lists

男娘i 2022-05-11 14:34 243阅读 0赞

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

hard

discuss中解法1：使用优先队列

/**
 * 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==null || lists.length==0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, new Comparator<ListNode>(){
            public int compare(ListNode l1, ListNode l2){
                return l1.val - l2.val;
            };
        });
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        //相当于初始化优先队列，将每一个链表的头结点放入队列，将会从小到大排序
        for(ListNode l : lists){
            if(l!=null)
                pq.offer(l);
        }
        //队列不为空时，tail指向队首，然后将弹出的队首所在链表看是否还有节点，有则继续加入队列
        //队列中每次只保留每个链表的头结点
        while(!pq.isEmpty()){
            tail.next = pq.poll();
            tail = tail.next;
            if(tail.next!=null){
                pq.offer(tail.next);
            }
        }
        return dummy.next;
    }
}

submission中解法2：分解成子问题，最终使用二分归并排序算法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return divide(lists, 0, lists.length - 1);
    }
    private ListNode divide(ListNode[] lists, int start, int end){
        if(start > end){
            return null;
        }
        if(start == end){
            return lists[start];
        }
        int mid = start + (end - start) / 2;
        ListNode left = divide(lists, start, mid);
        ListNode right = divide(lists, mid + 1, end);
        return merge(left, right);
    }
    private ListNode merge(ListNode l1, ListNode l2){
        ListNode head = new ListNode(0);
        ListNode curr = head;
        while(l1 != null || l2 != null){
            if(l1 != null && l2 != null){
                if(l1.val < l2.val){
                    curr.next = l1;
                    l1 = l1.next;
                }else{
                    curr.next = l2;
                    l2 = l2.next;
                }
            }else if(l1 != null){
                curr.next = l1;
                l1 = l1.next;
            }else{
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        return head.next;
    }
}