Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution:O(n)
public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if (lists.size() == 0) return null; Queue<ListNode> q = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>() { public int compare(ListNode a, ListNode b) { return (a.val-b.val); } }
); for (ListNode list : lists) { if (list != null) q.add(list); } ListNode head = new ListNode(0); ListNode prev = head; while (q.size() > 0) { ListNode temp = q.poll(); prev.next = temp; if (temp.next != null) q.add(temp.next);
prev = prev.next; } return head.next; } }
Key concept: Use PriorityQueue or heap to help get the smallest list. Use dummy node to avoid null.
沒有留言:
張貼留言