首页 > 代码库 > [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.
Solution 1:
PriorityQueue:
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * }10 * }11 */12 public class Solution {13 class myComparator implements Comparator<ListNode> {14 15 @Override16 public int compare(ListNode o1, ListNode o2) {17 // TODO Auto-generated method stub18 if (o1.val < o2.val) {19 return -1;20 } else if (o1.val > o2.val) {21 return 1;22 }23 return 0;24 }25 }26 27 public ListNode mergeKLists(List<ListNode> lists) {28 if(lists==null||lists.size()==0)29 return null;30 PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(),31 new myComparator());32 for (ListNode head : lists) {33 if (head != null) {34 pq.add(head);35 }36 }37 ListNode dummy = new ListNode(-1);38 ListNode cur = dummy;39 while (!pq.isEmpty()) {40 ListNode temp=pq.peek();41 pq.poll();42 cur.next=temp;43 cur=cur.next;44 if(temp.next!=null){45 pq.add(temp.next);46 }47 }48 return dummy.next;49 }50 }
Solution 2:
[Leetcode] Merge k Sorted Lists
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。