LeetCode 23 Merge k Sorted Lists

For this case, just compare k list’s first element, and put the smallest element int the new list. at the end, put the rest list’s all element on the tail of new list.

struct ListNode* findSmallest(struct ListNode** list, int listsSize) {
	int empty = 0;
	int head = -1;

	for (int i = 0; i < listsSize; i++) {
		if (list[i] == 0) {
			empty++;
			continue;
		}

		if (head == -1) {
			head = i;
			continue;
		}

		if (list[head]->val > list[i]->val) {
			head = i;
		}
	}

	struct ListNode* t_head = list[head];
	if (empty == listsSize)
		return 0;
	list[head] = list[head]->next;
	return t_head;

}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
	struct ListNode* head = malloc(sizeof(struct ListNode));
	struct ListNode* t_head = head;

	if (lists == 0 || listsSize == 0) {
		return 0;
	}

	while (1) {
		t_head->next = findSmallest(lists, listsSize);
		if (t_head->next == 0) {
			break;
		}
		printf("res:%d\n", t_head->next->val);
		t_head = t_head->next;
	}

	return head->next;
}