The title comes from LeetCode problem No. 23: Merge K sorted lists.

This question is marked as the most difficult one among the linked list problems on the official website of LeetCode: the difficulty is Hard, and the pass rate is the lowest in the Hard level of linked list.

Topic describes

Merge k sorted lists and return the merged sorted lists. Analyze and describe the complexity of the algorithm.

Example:

Input:1->4->5.1->3->4.2->6] output:1->1->2->3->4->4->5->6
Copy the code

The input

The output

Topic Analysis 1

So what we’re going to do is we’re going to combine these k sorted lists into one sorted list, which means we have multiple inputs and one output, kind of like a funnel.

Therefore, the concept of minimum heap can be used. If you are not familiar with the concept of heap, you can check it out

Take the smallest nodes of each Linked List and place them in a heap, sorting them into the smallest heap. It then takes the smallest element at the top of the heap, puts it into the output merged List, and then inserts that node into the heap the next node in its corresponding List, and so on until all nodes have passed through the heap.

Since the heap size is always K and the complexity of each insertion is logk, there are nk nodes inserted. The time complexity is O(Nklogk), and the space complexity is O(k).

The demo

Code implementation

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // Use the data structure heap, also known as the PriorityQueue in Java
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode a, ListNode b) {
                returna.val-b.val; }}); ListNode ret =null, cur = null;
        for(ListNode node: lists) {
            if(null != node) {
                pq.add(node);    
            }
        }
        while(! pq.isEmpty()) { ListNode node = pq.poll();if(null == ret) {
                ret = cur = node;
            }
            else {
                cur = cur.next = node;
            }
            if(null != node.next) {
                pq.add(node.next);    
            }
        }
        returnret; }}Copy the code

Analysis 2

This problem requires merging k ordered lists, and the result of merging must also be ordered. If you don’t have a clue at first, you can start with an easy one: merge two ordered lists.

Merge two ordered lists: Merge two ordered lists into a new ordered list and return. A new list is formed by concatenating all the nodes of a given two lists.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the code

Create a new linked list, compare the values of the two original linked lists, and add the smaller one to the new list. It should be noted that the lengths of the two input lists may be different, so one list will be inserted first and the other unfinished list will be directly linked to the end of the new list.

So the code implementation is easy to write:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a new list
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while(l1 ! =null&& l2 ! =null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else{ cur.next = l2; cur = cur.next; l2 = l2.next; }}// Note: when a linked list is empty, join another list directly
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return dummyHead.next;
    }
Copy the code

Now back to the original problem: merging K sorted linked lists.

The difference between merging K sorted lists and merging two ordered lists lies in the number of operations on ordered lists, so it is completely possible to merge K sorted lists according to the above code ideas.

Here we can refer to the divide-and-conquer idea of ** merge sort **, divide the K lists into two K/2 lists first, process their merge, and then continue to divide until only one or two linked lists are divided into tasks, and merge.

Code implementation

Based on the above animation, the implementation code is very simple and easy to understand, dividing until it can no longer be divided, and then merging.

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);
        }
        returnhead; }}Copy the code

Welcome to

Personal website: www.cxyxiaowu.com

Public number: five minutes to learn the algorithm