23 Merge K sorted Lists

最外层一个循环, 每次选取K个lists里面最小的元素，加到链表之中。 注意需要对于输入进行验证，判断输入为空的情况。

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        preHead = ListNode(-1)
        curNode = preHead
        length = len(lists)
        new_list = []
        if length == 0:
            return None
        for i in lists:
            if i is not None:
                new_list.append(i)
        while new_list:
            minVal, index = None, -1
            length = len(new_list)
            for l in range(length):
                if minVal is None or minVal > new_list[l].val:
                    minVal = new_list[l].val
                    index = l
            curNode.next = ListNode(minVal)
            curNode = curNode.next
            new_list[index] = new_list[index].next
            if new_list[index] is None:
                del new_list[index]
        return preHead.next

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue(new Comparator<ListNode>(){
            public int compare(ListNode o1, ListNode o2){
                return o1.val - o2.val;
            }
        });
        for (ListNode node:lists){
            if(node != null){
                heap.offer(node);
            }
        }

        ListNode pre = new ListNode(-1);
        ListNode temp = pre;
        while(!heap.isEmpty()){
            ListNode curr = heap.poll();
            temp.next = new ListNode(curr.val);
            if(curr.next != null){
                heap.offer(curr.next);
            }
            temp = temp.next;
        }
        return pre.next;
    }
}

编程知识点总结

• Java 实现优先队列（堆）：实际上是一个堆，队列的头是按照指定排序方法中的最小元素（数组）。

• 队列默认情况使用数组实现，但数组的大小可以动态增加，容量无限。

• 队列中不允许使用null元素

• 使用Comparator进行构建时，新的类需要实现Comparator接口，接口要求定义compare函数。

  PriorityQueue<ListNode> heap = new PriorityQueue(new Comparator<ListNode>(){
              public int compare(ListNode o1, ListNode o2){
                  return o1.val - o2.val;
              }
          });
  

• 常见方法

  • 添加方法：offer(E e), add(E e) 时间复杂度O(log(n))
  • 删除方法：remove(Object o), poll(E e)
  • 获取头元素：peek()
  • 获取大小：size()
  • 转成数组：toArray()
  • 是否包含：contains(Object o)
  • 全部清除：clear()
  • 通用方法：iterator(),comparator()