LeetCode——Merge k Sorted Lists

LeetCode——Merge k Sorted Lists

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

題目：歸並 k 個有序鏈表，返回一個有序鏈表。

思路：之前有做過歸並2個有序鏈表的題目，所以就想，將k個鏈表的歸並簡化成兩兩鏈表的歸並。

	public ListNode mergeKLists(List lists){
		if(lists == null)
			return null;
		return mergeLists(lists,0,lists.size()-1);
	}
	public ListNode mergeLists(List lists,int start,int end) {
		if(start > end)
			return null;
		if(start==end)
			return lists.get(start);
		if(start+1 == end)
			return mergeTwoLists(lists.get(start),lists.get(end));
		int mid = (start+end)/2;
		return mergeTwoLists(mergeLists(lists,start,mid),mergeLists(lists,mid+1,end));
	}
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode p1 = l1, p2 = l2, dummy = new ListNode(-1), p = dummy;
		while (p1 != null && p2 != null) {
			if (p1.val <= p2.val) {
				p.next = p1;
				p1 = p1.next;
			} else {
				p.next = p2;
				p2 = p2.next;
			}
			p = p.next;
		}
		if (p1 != null)
			p.next = p1;
		if (p2 != null)
			p.next = p2;
		return dummy.next;
	}
	// Definition for singly-linked list.
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}