LintCode 104. 合并k个排序链表

原题

解

第一步，万年不变的查错。如果给的list是null或空，直接return

    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.size() == 0) {
            return null;
        }
        ...
    }

最简单的方法当然还是PriorityQueue了，先建一个能比较node的PriorityQueue。

        Queue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

然后把每个list的头节点放进pq里面，顺便忽略null的list。其实这里也可以把list的每一个点放进去，不过这样会加大PriorityQueue的深度，也忽略了每个list都是排好序的特质。如果没有排过序，那么必须每个都放进去，既然现在排过了，就不需要在一开始就全放进去了。

        for (ListNode list : lists) {
            if (list != null) {
                pq.add(list);
            }
        }

然后就是从pq里面poll出最小的了。先建一个dummy用来存放开头的位置，然后一个current是跟着加入的node不断变的。每poll出一个，都要查看一下有没有next，如果有的话，再把next放回去。最后返回dummy的下一个，即开头的node就可以了。

        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        while (!pq.isEmpty()) {
            current.next = pq.poll();
            current = current.next;
            if (current.next != null) {
                pq.add(current.next);
                current.next = null;
            }
        }
        return dummy.next;

完整的code

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        Queue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        for (ListNode list : lists) {
            if (list != null) {
                pq.add(list);
            }
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        while (!pq.isEmpty()) {
            current.next = pq.poll();
            current = current.next;
            if (current.next != null) {
                pq.add(current.next);
                current.next = null;
            }
        }
        return dummy.next;
    }
}

解2

还可以用类似MergeSort的方式来做。每两个merge一个，然后产生一个新的list，再循环新的list，直到只剩一个（即MergeSort bottom up）。
完整的code

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        while (lists.size() != 1) {
            List<ListNode> newLists = new ArrayList<>();
            for (int i = 0; i + 1 < lists.size(); i+=2) {
                ListNode mergedList = merge(lists.get(i), lists.get(i + 1));
                newLists.add(mergedList);
            }
            if (lists.size() % 2 == 1) {
              newLists.add(lists.get(lists.size() - 1));
            }
            lists = newLists;
        }

        return lists.get(0);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
              current.next = l1;
              l1 = l1.next;
            } else {
              current.next = l2;
              l2 = l2.next;
            }
            current = current.next;
        }

        while (l1 != null) {
          current.next = l1;
          l1 = l1.next;
          current = current.next;
        }

        while (l2 != null) {
          current.next = l2;
          l2 = l2.next;
          current = current.next;
        }

        return dummy.next;
    }
}

解3

同样是merge，还可以用divide&conquer来做。merge左半边，再merge右半边，把两边最后再merge，跟MergeSort Top Down的想法是一样的。
完整的code

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        return mergeKHelper(lists, 0, lists.size() - 1);
    }

    private ListNode mergeKHelper(List<ListNode> lists, int start, int end) {
        if (start == end) {
          return lists.get(start);
        }

        int mid = start + (end - start) / 2;
        ListNode left = mergeKHelper(lists, start, mid);
        ListNode right = mergeKHelper(lists, mid + 1, end);

        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
              current.next = l1;
              l1 = l1.next;
            } else {
              current.next = l2;
              l2 = l2.next;
            }
            current = current.next;
        }

        while (l1 != null) {
          current.next = l1;
          l1 = l1.next;
          current = current.next;
        }

        while (l2 != null) {
          current.next = l2;
          l2 = l2.next;
          current = current.next;
        }

        return dummy.next;
    }
}

分析

时间复杂度

第一个方法，把k个list放进去要O(k)，把总共n个node拿出来每个要O(logk)，所以是O(nlogk)。第二个和第三个方法，都是使用类似于MergeSort的方法，排序总共n个数，每次把k个list平分，所以就是O(nlogk)。

空间复杂度

第一个方法是O(k)的复杂度。MergeSort是O(n)，因为它一直需要一个merge好的list/sublists。

总的来说，PriorityQueue更好一些吧。无论从时间，空间，实现的难易度来说，都是用PriorityQueue来做比较好。不过其它的也要会。