leetcode Merge k Sorted Lists 难度系数3 3.11

Question：

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

public class Solution {
	public ListNode mergeKLists(ArrayList<ListNode> lists) {
		if (lists.size() == 0) {
			return null;
		}
		if (lists.size() == 1) {
			return lists.get(0);
		}
		ListNode start = lists.get(0);
		for (int i = 1; i < lists.size(); i++) {
			start = mergeTwoLists(start, lists.get(i));
		}
		return start;
	}

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

	}
}

leetcode Merge k Sorted Lists 难度系数3 3.11

原文：http://blog.csdn.net/yiding_he/article/details/18893459