LeetCode 23. Merge k Sorted Lists ( C ) – Hard

這題是 LeetCode 21. Merge Two Sorted Lists 的延伸，把兩個鏈結串列 ( Linked List ) 增加到多個。

把多個鏈結串列 ( Linked List ) 依照大小排序，串接在一起，並回傳串接完的 Linked List。

原文題目如下

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.


Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:

Input: lists = []
Output: []
Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won't exceed 10^4

一開始我的想法是用迴圈每次找到最小的依序放入第一個 Linked List 中，但這個方法速度很慢，測試時大約花了 312 ms 的時間，後來我改用插入排序法的概念，依序讀每個 Linked List 中的值，一個個透過插入排序法插入 Linked List 中對應大小的位置，速度有著明顯的提升。

下面是我的程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {

	if (listsSize == 0)
		return NULL;
	for (int i = 1; i < listsSize; i++) {
		struct ListNode* ptrnow = lists[0], * ptrpost = lists[0];
		while (lists[i] != NULL) {
			if (ptrnow == NULL) {
				struct ListNode* temp = lists[i];
				lists[i] = lists[i]->next;
				temp->next = ptrnow;
				if (ptrpost != NULL) {
					ptrpost->next = temp;
					ptrpost = ptrpost->next;
				}
				else {
					lists[0] = temp;
					ptrpost = lists[0];
				}
			}
			else if (lists[i]->val < ptrnow->val) {
				struct ListNode* temp = lists[i];
				lists[i] = lists[i]->next;
				temp->next = ptrnow;
				if (ptrnow == lists[0]) {
					lists[0] = temp;
					ptrpost = lists[0];
				}
				else {
					ptrpost->next = temp;
					ptrpost = temp;
				}
			}
			else {
				if (ptrnow != lists[0]) {
					ptrpost = ptrpost->next;
				}
				ptrnow = ptrnow->next;
			}
		}
	}

	return lists[0];
}

下面是時間與空間之消耗

Runtime: 220 ms, faster than 60.37% of C online submissions for Merge k Sorted Lists.

Memory Usage: 8.1 MB, less than 96.50% of C online submissions for Merge k Sorted Lists.

下一題連結 :