LeetCode_23---Merge k Sorted Lists

Merge k Sorted Lists

  Total Accepted: 44376  Total Submissions: 210473 My Submissions

Question  Solution 

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

翻译：

Code:

package From21;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author MohnSnow
 * @time 2015年6月8日 上午10:51:35
 * 
 */
public class LeetCode23 {

	/**
	 * @param argsmengdx
	 *            -fnst
	 */
	//PriorityQueue is a sorted queue
	/*
	 * 优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
	 * PriorityQueue是从JDK1.5开始提供的新的数据结构接口。
	 * 如果不提供Comparator的话，优先队列中元素默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字典序排列。
	 * 由于网上的资料大多将优先级队列各个方法属性，很少有实例讲解的，为方便大家以后使用，我就写了个demo~
	 * 如果想实现按照自己的意愿进行优先级排列的队列的话，需要实现Comparator接口。下面的方法，实现了根据某个变量，来进行优先级队列的建立。
	 */
	static class ListNode {
		int			val;
		ListNode	next;

		ListNode(int x) {
			val = x;
		}

		@Override
		public String toString() {
			if (this.next != null) {
				return val + "---" + this.next.toString();
			} else {
				return val + "";
			}
		}
	}

	//397msA
	public static ListNode mergeKLists(ListNode[] lists) {
		int len = lists.length;
		if (len == 0) {
			return null;
		} else if (len == 1) {
			return lists[0];
		} else {
			ListNode[] newLists = new ListNode[(len + 1) / 2];
			for (int i = 0; i < newLists.length; i++) {
				int left = i, right = len - 1 - i;
				if (left == right) {
					newLists[i] = lists[i];
				} else {
					newLists[i] = mergeTwoLists(lists[left], lists[right]);
				}
			}
			return mergeKLists(newLists);
		}
	}

	public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
		if (list1 == null && list2 == null) {
			return null;
		}
		if (list1 == null && list2 != null) {
			return list2;
		}
		if (list1 != null && list2 == null) {
			return list1;
		}
		ListNode dummyHead = new ListNode(0);
		ListNode p1 = list1, p2 = list2, p3 = dummyHead;
		while (p1 != null && p2 != null) {
			if (p1.val <= p2.val) {
				p3.next = p1;
				p1 = p1.next;
			} else {
				p3.next = p2;
				p2 = p2.next;
			}
			p3 = p3.next;
		}
		p3.next = mergeTwoLists(p1, p2);//递归
		return dummyHead.next;
	}

	//480msA
	public static ListNode mergeKLists1(ListNode[] lists) {
		if (lists.length == 0)
			return null;
		PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length,
				new Comparator<ListNode>() {
					public int compare(ListNode a, ListNode b) {
						if (a.val > b.val)
							return 1;
						else if (a.val == b.val)
							return 0;
						else
							return -1;
					}
				});
		//add first node of each list to the queue
		for (ListNode list : lists) {
			if (list != null)
				q.add(list);
		}
		ListNode head = new ListNode(0);
		ListNode p = head; // serve as a pointer/cursor
		while (q.size() > 0) {
			ListNode temp = q.poll();
			//poll() retrieves and removes the head of the queue - q. 
			p.next = temp;
			//keep adding next element of each list
			if (temp.next != null)
				q.add(temp.next);
			p = p.next;
		}
		return head.next;
	}

	public static void main(String[] args) {
		ListNode a = new ListNode(1);
		ListNode b = new ListNode(2);
		ListNode c = new ListNode(3);
		ListNode d = new ListNode(4);
		ListNode e = new ListNode(5);
		a.next = b;
		b.next = c;
		c.next = d;
		d.next = e;
		e.next = null;
		ListNode f = new ListNode(3);
		ListNode g = new ListNode(9);
		ListNode h = new ListNode(11);
		f.next = g;
		g.next = h;
		h.next = null;
		ListNode i = new ListNode(4);
		ListNode j = new ListNode(9);
		ListNode k = new ListNode(110);
		i.next = j;
		j.next = k;
		k.next = null;
		ListNode[] lists = { a, g, i };
		System.out.println("第一种：" + mergeKLists(lists));
		System.out.println("第二种：" + mergeKLists1(lists));

	}

}