LeetCode 23. 合并K个排序链表

我的leetcode：

我的leetcode刷题源码[github]：https://github.com/izhoujie/algorithmcii

leetcode 23. 合并k个排序链表

题目

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

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

来源：力扣（leetcode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

很明显的topk问题；

• 使用最小堆或者优先队列；
• 分治，折半合并排序；

思路1-使用优先队列/最小堆

步骤：

1. 使用priorityqueue优先队列，需要实现comparator接口的compare方法；
2. 不断取出头部节点对象拼接新链表；

算法复杂度: n为节点总数

• 时间复杂度： $ {\color{magenta}{\omicron\left(nlogk\right)}} $
• 空间复杂度： $ {\color{magenta}{\omicron\left(k\right)}} $

思路2-分治折半合并排序

步骤：

1. 每次折半首位对应的链表合并排序，结果给到靠首部的位置；
2. 每次折半排序后的长度重置为（n+1）/2，解决长度为奇偶的问题；

算法复杂度: n为节点总数

• 时间复杂度： $ {\color{magenta}{\omicron\left(nlogk\right)}} $
• 空间复杂度： $ {\color{magenta}{\omicron\left(logk\right)}} $ 递归时栈的深度

算法源码示例

package leetcode;

import java.util.comparator;
import java.util.priorityqueue;

/**
 * @author zhoujie
 * @date 2020年1月10日 下午8:26:09 
 * @description: 23. 合并k个排序链表
 *
 */
public class leetcode_0023 {

}

// definition for singly-linked list.
class listnode_0023 {
	int val;
	listnode_0023 next;

	listnode_0023(int x) {
		val = x;
	}
}

class solution_0023 {
	/**
	 * @author zhoujie
	 * @date 2020年1月10日 下午8:48:38 
	 * @description: todo(方法简述) 
	 * @return listnode_0023 
	 * @updateuser-updatedate:[zhoujie]-[2020年1月10日 下午8:48:38]  
	 * @updateremark:1-使用优先队列
	 *
	 */
	public listnode_0023 mergeklists_1(listnode_0023[] lists) {
		if (lists == null) {
			return null;
		}
		// 优先队列，非基础类型需要重写比较器
		priorityqueue<listnode_0023> queue = new priorityqueue<listnode_0023>(new comparator<listnode_0023>() {
			public int compare(listnode_0023 o1, listnode_0023 o2) {
				return o1.val - o2.val;
			}
		});
		for (listnode_0023 node : lists) {
			if (node != null) {
				queue.add(node);
			}
		}
		listnode_0023 head, now;
		head = now = null;
		while (!queue.isempty()) {
			listnode_0023 node = queue.poll();
			if (head == null) {
				head = now = node;
			} else {
				now.next = node;
				now = node;
			}
			if (node.next != null) {
				queue.add(node.next);
			}
		}
		return head;
	}

	/**
	 * @author zhoujie
	 * @date 2020年1月10日 下午9:03:07 
	 * @description: todo(方法简述) 
	 * @return listnode_0023 
	 * @updateuser-updatedate:[zhoujie]-[2020年1月10日 下午9:03:07]  
	 * @updateremark:2-分治思想，不断折半合并，直至为一个；
	 *
	 */
	public listnode_0023 mergeklists_2(listnode_0023[] lists) {
		int len;
		if (lists == null || (len = lists.length) == 0) {
			return null;
		}
		while (len > 1) {
			for (int i = 0; i < len / 2; i++) {
				// 对半合并，后一半合并到前一半
				lists[i] = mergehelper(lists[i], lists[len - 1 - i]);
			}
			len = (len + 1) / 2;
		}
		return lists[0];
	}

	/**
	 * @author: zhoujie
	 * @date: 2020年2月4日 下午2:45:50 
	 * @param: @param l1
	 * @param: @param l2
	 * @param: @return
	 * @return: listnode_0023
	 * @description: 合并两个有序链表辅助方法
	 *
	 */
	private listnode_0023 mergehelper(listnode_0023 l1, listnode_0023 l2) {
		if (l1 == null) {
			return l2;
		} else if (l2 == null) {
			return l1;
		} else if (l1.val < l2.val) {
			l1.next = mergehelper(l1.next, l2);
			return l1;
		} else {
			l2.next = mergehelper(l1, l2.next);
			return l2;
		}
	}
}