23. Merge k Sorted Lists.md

23. Merge k Sorted Lists

Problem

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

tag:

• divider and conquer
• heap

Solution

solution1 : divide and conquner

java

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
			return null;
		return mergeHelper(lists, 0, lists.length - 1);
    }
    
    private ListNode mergeHelper(ListNode[] lists, int start, int end) {
		if (start == end) {
			return lists[start];
		}
		int mid = start + (end - start) / 2;
		ListNode left = mergeHelper(lists, start, mid);
		ListNode right = mergeHelper(lists, mid + 1, end);
		return mergeTwoLists(left, right);
	}

	private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode dummyHead = new ListNode(0);
		ListNode p = dummyHead;
		while (l1 != null && l2 != null) {
			if (l1.val < l2.val) {
				p.next = l1;
				l1 = l1.next;
			} else {
				p.next = l2;
				l2 = l2.next;
			}
			p = p.next;
		}
		if (l1 != null) p.next = l1;
		if (l2 != null) p.next = l2;
		return dummyHead.next;
	}

go

solution2 : heap

java

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length==0) return null;
        Queue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>(){
            public int compare(ListNode x, ListNode y) {
                return x.val-y.val;
            }
        } );
        for(ListNode node:lists) {
            if(node!=null) {
                queue.add(node);
            }
        }
        ListNode dummy = new ListNode(0), p = dummy;
        while(!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            p = p.next;
            if(node.next!=null) {
                queue.add(node.next);
            }
        }
        return dummy.next;
    }