LeetCode - Merge k Sorted Lists

Problem description

description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Analysis

This is a standard merge k list. At first, we can add first element of every list into a PriorityQueue, and we poll the smallest one and add the next ListNode of it into the PriorityQueue.

Here’s the code:

public class MergekSortedLists {
  public ListNode mergeKLists(ListNode[] lists) {
    ListNode dummy = new ListNode(0);

    int len = lists.length;
    PriorityQueue<ListNodeWrapper> pq = new PriorityQueue<>(new Comparator<ListNodeWrapper>() {
      @Override
      public int compare(ListNodeWrapper o1, ListNodeWrapper o2) {
        return o1.listNode.val - o2.listNode.val;
      }
    });

    for (int i = 0; i < len; i++){
      // wrong for this
      if (lists[i] != null){
        pq.offer(new ListNodeWrapper(lists[i], i));
      }
    }
    ListNode p = dummy;
    while (!isReachEnd(lists)){
      ListNodeWrapper next = pq.poll();
      int index = next.index;
      p.next = next.listNode;
      p = p.next;
      lists[index] = lists[index].next;
      if (lists[index] != null){
        pq.offer(new ListNodeWrapper(lists[index], index));
      }
    }

    return dummy.next;
  }

  boolean isReachEnd(ListNode[] lists){
    for(ListNode listNode:lists){
      if (listNode != null){
        return false;
      }
    }

    return true;
  }

  class ListNodeWrapper{
    ListNode listNode;
    int index;

    public ListNodeWrapper(ListNode l, int i){
      listNode = l;
      index = i;
    }
  }
}

Another solution from LeetCode is to use a divide and conquer method to divide the K lists into several groups of two lists and do the merge.

Here’s the code:

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return mergeHelper(lists, 0, lists.length - 1);
    }
    
    private ListNode mergeHelper(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        
        int mid = (start + end) / 2;
        ListNode left = mergeHelper(lists, start, mid);
        ListNode right = mergeHelper(lists, mid + 1, end);
        return mergeTwoSortedLists(left, right);
    }
    
    private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode res = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                res.next = l1;
                res = res.next;
                l1 = l1.next;
            } else {
                res.next = l2;
                res = res.next;
                l2 = l2.next;
            }
        }
        
        if (l1 != null) {
            res.next = l1;
        } else {
            res.next = l2;
        }
        
        return dummy.next;
    }
    
    void print(ListNode list){
        while(list!=null){
            System.out.print("" + list.val + "->");
            list = list.next;
        }
        
        System.out.println("null");
    }
}

What to improve

• null pointer check

• the index part is not necessary because we can use ListNode.next to find the next one should added into pq

• divide and conquer method is a way better solution than the PriorityQueue solution