20. 合并K个排序链表

<?php
Class ListNode {
    public $val = 0;
    public $next;
    public function __construct($val) {
        $this->val = $val;
    }
}
class Solution {
    // 分治
    public function mergeKLists1($lists) {
        return $this->handle($lists, 0, count($lists) - 1);
    }
    private function handle($list, $left, $right) {
        if ($left >= $right) return $list[$left];
        $mid = floor(($right - $left) / 2) + $left;
        $l1 = $this->handle($list, $left, $mid);
        $l2 = $this->handle($list, $mid + 1, $right);
        return $this->mergeTwoLists($l1, $l2);
    }
    private function mergeTwoLists(ListNode $l1, ListNode $l2) : ListNode {
        if (!$l1) return $l2;
        if (!$l2) return $l1;
        $dummyHead = new ListNode(0);
        $current = $dummyHead;
        while ($l1 || $l2) {
            if (!$l1) {
                $current->next = $l2;
                break;
            }
            if (!$l2) {
                $current->next = $l1;
                break;
            }
            if ($l1->val < $l2->val) {
                $current->next = $l1;
                $current = $current->next;
                $l1 = $l1->next;
            } else {
                $current->next = $l2;
                $current = $current->next;
                $l2 = $l2->next;
            }
        }
        return $dummyHead->next;
    }
    // 小顶堆
    public function mergeKLists2($lists) {
        $dummyHead = new ListNode(0);
        $current = $dummyHead;
        $minHeap = new SplMinHeap();
        if ($lists) {
            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) {
                $current->next = $l;
                $current = $current->next;
            }
        }
        return $dummyHead->next;
    }
}
$elem1 = new ListNode(1);
$elem1->next = new ListNode(4);
$elem1->next->next = new ListNode(5);
$elem2 = new ListNode(1);
$elem2->next = new ListNode(3);
$elem2->next->next = new ListNode(4);
$elem3 = new ListNode(2);
$elem3->next = new ListNode(6);
$lists = [$elem1, $elem2, $elem3];
$cls = new Solution();
// 分治
// $r = $cls->mergeKLists1($lists);
// print_r($r);
// 小顶堆
$r = $cls->mergeKLists2($lists);
print_r($r);