Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
leetcode上返回类型不太一样,改编一下第三个解法:4ms
public class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } ListNode[] newlists = new ListNode[0]; while(lists.length>1) { if(lists.length%2==0) { newlists = new ListNode[lists.length/2]; for(int i=0;i<lists.length-1;i += 2) { ListNode node = mergeTwoLists(lists[i],lists[i+1]); newlists[i/2] = node; } } else { newlists = new ListNode[lists.length/2+1]; for(int i=0;i<lists.length-1;i += 2) { ListNode node = mergeTwoLists(lists[i],lists[i+1]); newlists[i/2] = node; } newlists[newlists.length-1] = lists[lists.length-1]; } lists = newlists; } return lists[0]; } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyhead = new ListNode(0); ListNode head = dummyhead; while(l1!=null&&l2!=null) { if(l1.val<l2.val) { head.next = l1; l1 = l1.next; } else { head.next = l2; l2 = l2.next; } head = head.next; } if(l1!=null) head.next = l1; if(l2!=null) head.next = l2; return dummyhead.next; } }
解法二:用heap, 12ms, 时间复杂度O(nlog(k))
Suppose the total number of nodes is n The total time complexity if (n * log k) .For a priority queue, insertion takes logK time
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() { public int compare(ListNode left, ListNode right) { if (left == null) { return 1; } else if (right == null) { return -1; } return left.val - right.val; } }; public ListNode mergeKLists(ListNode[] lists) { if(lists==null||lists.length==0)return null; Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,ListNodeComparator); for(int i=0;i<lists.length;i++) { if(lists[i]!=null) { heap.add(lists[i]); } } ListNode dummy = new ListNode(0); ListNode tail = dummy; while(!heap.isEmpty()) { ListNode head = heap.poll(); tail.next = head; tail = head; if (head.next != null) { heap.add(head.next); } } return dummy.next; } }