Leetcode Merge k Sorted Lists 使用递归解决

一开始，我使用了二分法进行两两合并

while (n >= 1) {
	for (int i=0; i<n/2; i++) {
		lists[i] = mergeTwoLists(lists[i], lists[n-i-1]);
	}
	if (n % 2 == 0 ) {
		n /= 2;
	} else {
		n = n /2 + 1;
}

不过这样以来是双重循环，复杂度有点高，因此出现了Runtime error

递归解决
在使用递归解决时，可以利用二叉树的思想来解决此问题
可以把给出的链表拆分成下面的二叉树

这样融合的过程为

1. B + C = BC
2. BC + A = ABC
3. E + F = EF
4. EF + D = EFD
5. ABC + EFD = 结果

也可以使用(result (A (B C)) (D (E F))解释上面的融合过程
完整代码

typedef struct ListNode Node;
Node* partion(Node** lists, int start, int end);
Node* mergeTwoLists(Node* l1, Node* l2);

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    return partion(lists, 0, listsSize-1);
}

Node* partion(Node** lists, int start, int end) {
    if (start == end)
        return lists[start];
    if (start < end) {
        int middle = (start + end) / 2;
        Node* l1 = partion(lists, start, middle);
        Node* l2 = partion(lists, middle+1, end);
        return mergeTwoLists(l1, l2);
    } else {
        return NULL;
    }
}

Node* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1 == NULL && l2 == NULL)
        return NULL;
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;
    Node* new_node;
    if (l1->val >= l2->val) {
        new_node = l2;
        new_node->next = mergeTwoLists(l1, l2->next);
    } else {
        new_node = l1;
        new_node->next = mergeTwoLists(l1->next, l2);
    }
    return new_node;
}