Merge k Sorted Lists (H)

Merge k Sorted Lists (H)

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

meaning of the title

The k ordered lists are merged into an ordered list.

thinking

Similar to the two-way merge method, the priority queue can be used to find the smallest of k nodes.

It is also possible to divide all linked lists into several groups and merge them into two routes at a time, and finally merge them into a large list.

The time complexity of the two methods is O(Nlogk)O(Nlogk)O(Nlogk), but the running time is quite different after actual submission. The reason may be that in the priority queue method, each node needs to be connected to a new list separately. In the divide-and-conquer method, when one of the two lists is null, the remaining nodes in the other list can be connected directly to the new list and omitted. Part of the time.

Code Implementation - Priority Queue

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(0);
        ListNode pointer = head;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(((o1, o2) -> o1.val - o2.val));
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                pq.offer(lists[i]);
            }
        }
        while (!pq.isEmpty()) {
            pointer.next = pq.poll();
            pointer = pointer.next;
            if (pointer.next != null) {
                pq.offer(pointer.next);
            }
        }
        return head.next;
    }
}

Code implementation-divide and conquer

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // Exclude special cases first, otherwise array subscripts will overflow
        if (lists.length == 0) {
            return null;
        }
        for (int step = 1; step < lists.length; step *= 2) {
            for (int i = 0; i + step < lists.length; i += 2 * step) {
                lists[i] = mergeTwo(lists[i], lists[i + step]);
            }
        }
        return lists[0];
    }

    private ListNode mergeTwo(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode pointer = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                pointer.next = l1;
                l1 = l1.next;
            } else {
                pointer.next = l2;
                l2 = l2.next;
            }
            pointer = pointer.next;
        }
        pointer.next = l1 == null ? l2 : l1;
        return head.next;
    }
}

Posted on Sat, 05 Oct 2019 22:56:14 -0700 by torvald_helmer