23 - Merge k Sorted Lists

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

Algorithm

“big-o analysis time-complex O(NKlogK)

        public ListNode merge(ListNode[] lists, int start, int end) {

            int mid = (end - start) / 2 + start;
            ListNode leftHalf = merge(lists, start, mid);
            ListNode rightHalf = merge(lists, mid + 1, end);

heap解法：heap.offer(polled.next); 这里heap的offer()参数不能是null，因为要保证polled不是null，才能更新currentNode

            if (polled.next != null) {
                heap.offer(polled.next); // @note: offer()参数不能是null
            }

Code

MergeSort 解法

public class Merge_k_Sorted_Lists {

	public static void main(String[] args) {

		Merge_k_Sorted_Lists out = new Merge_k_Sorted_Lists();
		Solution s = out.new Solution();

		ListNode l1 = null;
		ListNode l2 = new ListNode(1);

		s.mergeKLists(new ListNode[]{l1, l2});

	}


	/**
	 * Definition for singly-linked list.
	 * public class ListNode {
	 *     int val;
	 *     ListNode next;
	 *     ListNode(int x) { val = x; }
	 * }
	 */

	// ref: https://leetcode.com/articles/merge-k-sorted-list/
    // Time complexity : O(Nlogk) where k is the number of linked lists, n is total nodes count
        // k/2 + k/4 + k/8 + ... = logK
    // Space complexity : O(1)


    // 2n * k/2 + 4n * k/4 + ... + (2^x)n * k/(2^x) = nk * x
    //    k/(2^x) = 1 -> 2^x = k -> x = log2(k)
    // 所以时间复杂度为O(nk log(k))，与方法一相同。

    public class Solution {
	    public ListNode mergeKLists(ListNode[] lists) {

	        if (lists == null || lists.length == 0) {
	            return null;
	        }

	        // same as merge sort array
	        return merge(lists, 0, lists.length - 1);
	    }

	    public ListNode merge(ListNode[] lists, int start, int end) {

	        // single list
	        if (start == end) {
	            return lists[start];
	        }

	        int mid = (end - start) / 2 + start;
	        ListNode leftHalf = merge(lists, start, mid);
	        ListNode rightHalf = merge(lists, mid + 1, end);

	        return mergeTwoLists(leftHalf, rightHalf);
	    }

	    // from previous question: 21 Merge Two Sorted Lists
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

	        ListNode dummy = new ListNode(0);
	        ListNode current = dummy;

	        while (l1 != null || l2 != null) {
	            int v1 = (l1 == null? Integer.MAX_VALUE : l1.val);
	            int v2 = (l2 == null? Integer.MAX_VALUE : l2.val);

	            if (v1 < v2) {
	                current.next = l1;
	                l1 = l1.next;
	            } else {
	                current.next = l2;
	                l2 = l2.next;
	            }

	            current = current.next; // now current is the new end node, but still pointing to next node
	            current.next = null; // @note: key, cut this node from l1 or l2
	        }

	        return dummy.next;
	    }
	}



}

heap解法

	/*
	    heap解法

            将每个list的最小节点放入一个priority queue (min heap)中。
            之后每从queue中取出一个节点，则将该节点在其list中的下一个节点插入，
            以此类推直到全部节点都经过priority queue。

            由于priority queue的大小为始终为k，而每次插入的复杂度是log k，一共插入过nk个节点。
            时间复杂度为O(nk logk)，空间复杂度为O(k)。

	 */

    class Solution_Heap {
        public ListNode mergeKLists(ListNode[] lists) {

            if (lists == null || lists.length == 0) {
                return null;
            }

            ListNode dummy = new ListNode(0);
            ListNode current = dummy;

            // put 1st of each list to heap
            PriorityQueue<ListNode> heap = new PriorityQueue<>(
                (a,b) -> a.val - b.val
            );

            //
            Arrays.stream(lists).filter(Objects::nonNull).forEach(heap::offer);

            while (heap.size() != 0) {
                ListNode polled = heap.poll();

                current.next = polled;
                current = current.next;

                if (polled.next != null) {
                    heap.offer(polled.next); // @note: heap.offer()参数不能是null
                }
            }

            return dummy.next;
        }
    }