Java solution using minHeap / PriorityQueue


  • 0
    B

    /**

    • Definition for singly-linked list.
    • public class ListNode {
    • int val;
      
    • ListNode next;
      
    • ListNode(int x) { val = x; }
      
    • }
      */
      public class Solution {
      public ListNode mergeKLists(ListNode[] lists) {
      if (lists == null || lists.length == 0) {
      return null;
      }
      int n = lists.length;
      PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(n, new Comparator<ListNode>(){
      @Override
      public int compare(ListNode o1, ListNode o2) {
      if (o1.val == o2.val) {
      return 0;
      }
      return o1.val < o2.val ? -1 : 1;
      }
      });
      for (int i = 0; i < n; i++) {
      if (lists[i] != null) {
      minHeap.offer(lists[i]);
      }
      }
      ListNode dummyHead = new ListNode(0);
      ListNode cur = dummyHead;
      while (!minHeap.isEmpty()) {
      cur.next = minHeap.poll();
      cur = cur.next;
      if (cur . next != null) {
      minHeap.offer(cur.next);
      }
      }
      return dummyHead.next;
      }
      }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.