23. 合并K个排序链表

题意：

解题思路：

思路：
    1. 分治合并；O(nlogk) //同21.合并两个有序链表 相关联
    2. 小顶堆；每次O(logK)，比较K个指针求min, 时间复杂度：O(NlogK)

PHP代码实现：

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {
    /**
     * @param ListNode[] $lists
     * @return ListNode
     */
    function mergeKLists($lists) {
        $left = 0; $right = count($lists);
        return $this->merge($lists, $left, $right);
    }
    function merge($list, $left, $right) {
        if ($left >= $right) return $list[$left];
        $mid = $left + floor(($right - $left) >> 1);
        $l1 = $this->merge($list, $left, $mid);
        $l2 = $this->merge($list, $mid + 1, $right);
        return $this->mergeTwoSortedLists($l1, $l2);
    }
    function mergeTwoSortedLists($l1, $l2) {
        $dummy = new ListNode(0);
        $cur = $dummy;
        while ($l1 != null && $l2 != null) {
            if ($l1->val <= $l2->val) {
                $cur->next = $l1;
                $l1 = $l1->next;
            } else {
                $cur->next = $l2;
                $l2 = $l2->next;
            }
            $cur = $cur->next;
        }
        $cur->next = $l1 == null ? $l2 : $l1;
        return $dummy->next;
    }
    //小顶堆
    function mergeKLists($lists) {
        if (count($lists) == 0) return;
        $dummy = new ListNode(0);
        $cur = $dummy;
        $minHeap = new SplMinHeap;
        foreach ($lists as $l) $minHeap->insert($l);
        while (!$minHeap->isEmpty()) {
            $l = $minHeap->top();
            $minHeap->next();
            if ($l->next != null) $minHeap->insert($l->next);
            if ($l) {
                $cur->next = $l;
                $cur = $cur->next;
            }
        }
        return $dummy->next;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    if 0 == len(lists) { return nil }
    return merge(lists, 0, len(lists) - 1)
}
func merge(lists []*ListNode, left, right int) *ListNode {
    if left == right {
        return lists[left]
    }
    mid := left + (right - left) / 2
    l1 := merge(lists, left, mid)
    l2 := merge(lists, mid+1, right)
    return mergeTwoSortedLists(l1, l2)
}
func mergeTwoSortedLists(l1 *ListNode, l2 *ListNode) *ListNode {
   dummy := &ListNode{}
   cur := dummy
   for l1 != nil && l2 != nil {
      if l1.Val < l2.Val {
         cur.Next = l1
         l1 = l1.Next
      } else {
         cur.Next = l2
         l2 = l2.Next
      }
      cur = cur.Next
   }
   if l1 != nil {
      cur.Next = l1
   }
   if l2 != nil {
      cur.Next = l2
   }
   return dummy.Next
}