首页 > 代码库 > [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