p23

 

public class  {
   public static ListNode mergeKLists(ListNode[] lists) {
		ListNode ans = new ListNode(Integer.MIN_VALUE);

		
		int len = lists.length;
		if (len < 1)
			return null;
		if (len == 1)
			return lists[0];

		return mergeKLists(lists, 0, len - 1);
	}

	public static ListNode mergeKLists(ListNode[] lists, int left, int right) {
		if (left == right)
			return lists[left];
		ListNode ans = new ListNode(Integer.MIN_VALUE);

		int mid = (left + right) / 2;
		return mergeTwoLists(mergeKLists(lists, left, mid),
				mergeKLists(lists, mid + 1, right));// 用递归不然会超时
	}

	public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null) {
			return l2;
		}
		if (l2 == null) {
			return l1;
		}
		ListNode ans = new ListNode(0);

		ListNode node = ans;

		while (l1 != null && l2 != null) {
			if (l1.val >= l2.val) {
				node.next = l2;

				l2 = l2.next;
			} else {
				node.next = l1;
				l1 = l1.next;
			}
			// System.out.println(node.val);
			node = node.next;
		}
		node.next = (l1 != null) ? l1 : l2;

		return ans.next;
	}
}