LeetCode(23) - 合并 K 个排序链表

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[
  1->4->5,
  1->3->4,
  2->6
]

输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题说明

类似快速幂的思路，使用分治的思想，先两两合并，合并完了之后再两两合并，这样对于 k 个链表就只需要合并 $log_2k$ 次，总的复杂度就是 $n\times{\log_2k}$

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
    	if(lists.length == 0) {
    		return null;
    	}
    	return merge(lists, 0, lists.length-1);
    }

	private ListNode merge(ListNode[] lists, int start, int end) {
    	if (start >= end) {
    		return lists[start];
    	}  
    	if((end - start) == 1) {
    		return merge(lists[start], lists[end]);
    	} 

    	int mid = start + (end - start + 1) / 2;
    	ListNode l1 = merge(lists, start, mid -1);
    	ListNode l2 = merge(lists, mid, end);
    	return merge(l1, l2);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
    	ListNode res = new ListNode(0);
    	ListNode p = res;

    	while(l1 != null || l2 != null) {
    		if (l1 == null) {
    			p.next = new ListNode(l2.val);
    			l2 = l2.next;
    		} else if (l2 == null) {
    			p.next = new ListNode(l1.val);
    			l1 = l1.next;
    		} else if (l1.val < l2.val) {
    			p.next = new ListNode(l1.val);
    			l1 = l1.next;
    		} else {
    			p.next = new ListNode(l2.val);
    			l2 = l2.next;
    		}
    		p = p.next;
    	}

    	return res.next;
    }
}